【恋上数据结构】复杂度知识以及 LeetCode 刷题指南

简介: 本文主要介绍复杂度相关知识,以及的对 LeetCode 刷题方法做一个简单的介绍
感谢小码哥的 恋上数据结构,记录课程笔记。

什么是算法?

算法是用于解决特定问题的一系列的执行步骤。

以下算法是为了解决两数相加的问题:

// 计算a和b的和
public static int plue(int a, int b){
    return a + b;
}

以下算法是为了解决 n个数字的和 的问题:

// 1+2+3+...+n
public static int sum(int n){
    int result = 0;
    for(int i = 1; i <= n; i++){
        result += i;
    }
    return result;
}

使用不同算法,解决同一个问题,效率可能相差非常大。比如:

  • 求第 n 个斐波那契数(fibonacci number)

如何评判一个算法的好坏?

如果单从执行效率上进行评估,可能会想到这么一种方案:

  • 比较不同算法对同一组输入的执行处理时间
  • 这种方案也叫做:事后统计法

上述方案有比较明显的缺点:

  • 执行时间严重依赖硬件以及运行时各种不确定的环境因素
  • 必须编写相应的测算代码
  • 测试数据的选择比较难保证公正性

一般从以下维度来评估算法的优劣:

  • 正确性、可读性、健壮性(对不合理输入的反应能力和处理能力)
  • 时间复杂度(time complexity):估算程序指令的执行次数(执行时间)
  • 空间复杂度(space complexity):估算所需占用的存储空间

由于现在硬件发展的较好,一般情况下我们更侧重于时间复杂度


下面代码是一个测试时间效率的小工具:

package com.mj;

import java.text.SimpleDateFormat;
import java.util.Date;

/**
 * 测试时间效率的小工具
 */
public class Times {
    private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS");
    
    public interface Task {
        void execute();
    }
    
    public static void test(String title, Task task) {
        if (task == null) return;
        title = (title == null) ? "" : ("【" + title + "】");
        System.out.println(title);
        System.out.println("开始:" + fmt.format(new Date()));
        long begin = System.currentTimeMillis(); // 开始时间
        task.execute(); // 执行代码
        long end = System.currentTimeMillis(); // 结束时间
        System.out.println("结束:" + fmt.format(new Date()));
        double delta = (end - begin) / 1000.0; // 毫秒转换为秒
        System.out.println("耗时:" + delta + "秒");
        System.out.println("-------------------------------------");
    }
}

大O表示法(Big O)

一般用大O表示法来描述复杂度,它表示的是数据规模 n 对应的复杂度。

忽略常数、系数、低阶:

  • 9 >> O(1)
  • 2n + 3 >> O(n)
  • n^2^ + 2^n^ + 6 >> O(n^2^)
  • 4n^3^ + 3n^2^ + 22n + 100 >> O(n^3^)
  • 写法上,n^3^ 等价于 n^3

注意:大O表示法仅仅是一种粗略的分析模型,是一种估算,能帮助我们短时间内了解一个算法的执行效率。

对数阶的细节

对数阶一般省略底数:

  • 由于 log~2~^9^ ∗ log~9~^n^ >> log~2~^n^,即每个对数基本都可以常数乘另一个对数
  • 所以 O(log~2~^n^) 、O(log~9~^n^) 统称为 O(log^n^)

常见的复杂度

在这里插入图片描述
在这里插入图片描述

可以借助函数生成工具对比复杂度的大小: https://zh.numberempire.com/graphingcalculator.php

在这里插入图片描述

在这里插入图片描述

多个数据规模的情况

时间复杂度:O(n + k)

public static void test(int n, int k){
    for(int i = 0; i < n; i++){
        System.out.println("test");
    }
    for (int i = 0; i < k; i++){
        System.out.println("test");
    }
}

LeetCode刷题指南

首先去 https://leetcode-cn.com/ 注册一个力扣账号。

我们以力扣上一道斐波那契的题目为例,顺便分析算法的时间复杂度。
题目网址:LeetCode: 509.斐波那契数

在这里插入图片描述
以执行 斐波那契数列(递归) 为例,必须写成这样:
在这里插入图片描述

斐波那契数列复杂度分析

斐波那契数列 - 递归

很简单的代码,相信来学数据结构的同学都能看懂。

// O(2^n)
public static int fib1(int n) {
    if (n <= 1) return n;
    return fib1(n - 1) + fib1(n - 2);
}

复杂度分析:
在这里插入图片描述

我们放到力扣上去执行一下:效率奇差无比!
在这里插入图片描述

斐波那契数列 - 循环

不开辟任何空间,只使用循环完成。

// O(n)
public static int fib2(int n) {
    if (n <= 1) return n;
    
    int first = 0;
    int second = 1;
    for (int i = 0; i < n - 1; i++) {
        int sum = first + second;
        first = second;
        second = sum;
    }
    /*
    // 也可以使用while循环
    while (n-- > 1) {
        second += first;
        first = second - first;
    }
    */
    return second;
}

力扣上执行:速度变快了,内存消耗还是很多....
在这里插入图片描述

开辟新的数组空间,用空间换时间。

public static int fib3(int n){
    if(n <= 1) return n;
    
    int[] fib = new int[n+1];
    fib[0] = 0;
    fib[1] = 1;
    for(int i = 2; i < fib.length; i++){
        fib[i] = fib[i-1] + fib[i-2];
    }
    return fib[n];
}

力扣上执行:呃,和上面好像没啥区别。。
在这里插入图片描述

fib函数的时间复杂度分析

上面两种 fib 函数的差别有多大?

  • 如果有一台 1GHz 的普通计算机,运算速度 10^9^ 次每秒,n 为 64
  • O(n) 大约耗时 6.4 $*$ 10^-8^
  • O(2^n^) 大约耗时 584.94
  • 有时候算法之间的差距,往往比硬件方面的差距还要大

斐波那契的线性代数解法-特征方程

在这里插入图片描述

算法的优化方向

  • 用尽量少的存储空间
  • 用尽量少的执行步骤(执行时间)
  • 根据情况:空间换时间时间换空间

后序

【恋上数据结构】数据结构大全

相关文章
|
1月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
73 2
|
1月前
|
机器学习/深度学习 存储 算法
【初阶数据结构篇】时间(空间)复杂度
复杂度是计算机科学中的一个基础概念,它帮助我们理解和评估算法的效率,对于算法设计和优化至关重要。
【初阶数据结构篇】时间(空间)复杂度
|
1月前
|
算法
【初阶数据结构】复杂度算法题篇
该方法基于如下的事实:当我们将数组的元素向右移动 k 次后,尾部 kmodn 个元素会移动至数组头部,其余元素向后移动 kmodn 个位置。
|
1月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
36 7
|
1月前
|
算法 Python
【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
本文介绍了LeetCode 2038题的解法,题目要求在一个由'A'和'B'组成的字符串中,按照特定规则轮流删除颜色片段,判断Alice是否能够获胜,并提供了Python的实现代码。
36 3
|
1月前
|
算法 Python
【Leetcode刷题Python】剑指 Offer 33. 二叉搜索树的后序遍历序列
本文提供了一种Python算法,用以判断给定整数数组是否为某二叉搜索树的后序遍历结果,通过识别根节点并递归验证左右子树的值是否满足二叉搜索树的性质。
15 3
|
1月前
|
Python
【Leetcode刷题Python】50. Pow(x, n)
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
15 1
|
1月前
|
Python
【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
本文介绍了LeetCode 478题的解法,题目要求在给定圆的半径和圆心位置的情况下实现在圆内均匀随机生成点的功能,并提供了Python的实现代码。
17 1
|
1月前
|
算法 Python
【Leetcode刷题Python】295. 数据流的中位数
本文介绍了一种使用Python实现的数据结构,用以支持数据流中添加整数并返回当前所有元素的中位数,通过排序列表来计算中位数。
14 1
|
1月前
|
算法 Python
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
17 0
【Leetcode刷题Python】73. 矩阵置零