复杂度

什么是算法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
// 计算a和b的和
public static int plue(int a, int b){
	return a + b;
}

// 计算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）：估算所需占用的存储空间
1
2
3
4
5
6
7
8
9
10
11
12
13
// 计算 1+2+3+...+n 的和
public static int sum1(int n) {
    int result = 0;
    for (int i = 1; i <= n; i++) {
        result += i;
    }
    return result;
}

// 计算 1+2+3+...+n 的和
public static int sum2(int n) {
    return (1 + n) * n / 2;
}

大O表示法（Big O）

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

忽略常数、系数、低阶

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

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

对数阶的细节

对数阶一般省略底数

所以 log2n 、log9n 统称为 logn

常见的复杂度

  • O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2n) < O(n!) < O(n^n)
  • 可以借助函数生成工具对比复杂度的大小
  • https://zh.numberempire.com/

数据规模较小时

数据规模较大时

fib函数的时间复杂度分析

  • 呈现的是指数级增长的趋势

fib函数的时间复杂度分析

O(2^n)

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

O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 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;
    }
    return second;
}

public static int fib3(int n) {
    if (n <= 1) return n;

    int first = 0;
    int second = 1;
    while (n-- > 1) {
        second += first;
        first = second - first;
    }
    return second;
}

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

1
2
3
4
public static int fib4(int n){
    double c = Math.sqrt(5);
    return (int)((Math.pow((1 + c) / 2,n) - Math.pow((1 - c) / 2, n)) / c);
}

时间复杂度：视为 O(1)

算法的优化方向

用尽量少的存储空间

用尽量少的执行步骤（执行时间）
根据情况，可以

  • 空间换时间
  • 时间换空间

多个数据规模的情况

1
2
3
4
5
6
7
8
9
public static void test(int n,int k){
    for (int i = 0; i < n; i++){
        System.out.println("test");
    }
    
    for (int k = 0; k < n; k++){
        System.out.println("test");
    }
}

O(n + k)

leetcode

一个用于练习算法的好网站

  • https://leetcode.com/
  • https://leetcode-cn.com/

斐波那契数

  • https://leetcode-cn.com/problems/fibonacci-number/