第0章. 时空复杂度

时空复杂度

一、时间复杂度

• 时间复杂度：估算程序指令的执行次数(执行时间)

1.1 大O表示法(Big O)

• 一般用大O表示法来描述复杂度，它表示的是数据规模n对应的复杂度
• 它并不是用于来真实代表算法的执行时间，它是用来表示代码执行时间的增长变化趋势的
• 忽略常数、系数、低阶
  • 9 —— O(1)
  • 2 n + 3 —— O(n)
  • n² + 2 n + 6 —— O(n²)
  • 4 n³ + 3 n² + 22 n + 100 —— O(n³)

1.2 对数阶的细节

• 对数阶一般省略底数，统称为O(log n)

问题：算法时间复杂度为什么用"log n"，而不用"log₂n"，"lg n"

原因：

假如有log_ab，由换底公式可得：

log_ca（c为底数）为常数，

由O的运算规则"O( C × f(N) )=O( f(N ) )，

其中C是一个正的常数"

得O（log_ab）=O（log_cb）

可知算法的时间复杂度与不同底数只有常数的关系，而常数在大O表示法中可以省略,自然可以用log N代替。

例如：log₂n = log₂9 · log₉n

O(log₂n) = O(log₂9 · log₉n) = O(log₉n)

可知不同底数的算法时间复杂度只有常数的关系，而常数在大O表示法中可以省略，自然可以用log N代替。

1.3 常见的时间复杂度排序

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2^) < O(n^3^) < O(2^n^) < O(n!) < O(n^n^)

1.4 多个数据规模的情况

public 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");
    }
}
// 时间复杂度为:O(n + k)

1.5 时间复杂度举例

public void test(int n) {
    int i = 1;
    while(i < n)
    {
        i = i * 2;
    }
}

• 设循环执行k次,则k次后i的值为2^k，退出循环的条件是2^k == n，可以算出k= log₂n 时退出循环
• 即这个算法执行的总次数= 1 + (k + 1) + k = 2 k + 2 = 2 log₂n + 1
• 根据大O表示法这个算法的时间复杂度为O(log n)

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

• 内层循环执行的次数1 + 16 + 15 + 15 = 47次
• 外层循环执行1 + (n + 1) + n = 2 n + 2次
• 则一共执行(2 n + 2) * 47 = 94(n + 1)
• 根据大O表示法这个算法的时间复杂度为O(n)

public int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 2) + fib(n - 1);
}

• 算法的核心代码就是fib(n - 2) + fib(n - 1)
• 这个算法执行多少次就取决于fib函数被调用多少次
• 例如n = 5，画出递归树

二、空间复杂度

• 空间复杂度：估算算法所需占用的存储空间

2.1 常见的空间复杂度

• O(1)

int i = 1;
int j = 2;
int m = i + j;

• O(n)

int[] arr = new int[n];
for(int i = 0; i < arr.length; i ++) {
    arr[i] = i;
}