从零开始算法入门——0时间复杂度

时间复杂度

1. 什么是时间复杂度

衡量一个算法的快慢，一定要考虑数据规模的大小。所谓数据规模，一般指输入的数字的个数，输入的图的点数和边数等等。一般来说数据规模越大，算法用时越长。在算法竞赛中，我们衡量一个算法的效率时，最重要的不是看它在某个数据规模下的用时，而是看它的用时随数据规模而增长的趋势，即时间复杂度。
时间复杂度一般用O表示，例如：O(1),O(n)等。在分析时间复杂度时，一般会忽略掉常数项的影响，例如若一个算法执行次数是${\frac{n^2}{2}}$，他的时间复杂度是$O(n^2)$而不是$O({\frac{n^2}{2}})$

2. 常见时间复杂度

$O(1)$

O(1)并不是指一次运算而是指常数级运算。

int x = 1;
printf("%d",x);

执行次数1次，时间复杂度O(1)。

$O(\log n)$

int n = 10000;
while (n) 
{
    n = n / 2;
}

假设执行k次，则有$\frac{n}{2^k} \approx 1$,即$k \approx \log_2 n$，所以时间的复杂度为$O(\log n)$。

$O(n)$

int n = 100000,x = 0;
for (int i = 0;i < n;i++) 
{
    x++;
}

执行次数n次，时间复杂度为$O(n)$。

$O(n \log n)$

int n = 100000,x = 0;
for (int i = 1;i <= n;i++) 
{
    for (int j = i;j <= n;j += i) 
    {
        x++;
    }
}

注：不要看到双重for循环就以为是$O(n^2)$,对于这段代码，当i等于1时，j从1到n，每次加1，运行n次；当i等于2时，j从2到n，每次加2，运行$\frac{n}{2}$次…当i等于n时，j从n到n，运行1次。总运算次数为$\sum_{i=1}^{n} \frac{n}{i}$ ,即 $n\sum_{i=1}^{n} \frac{1}{i}$。
对于$\sum_{i=1}^{n} \frac{1}{i}$，大家以后学高数的时候应该会接触到，它就是大名鼎鼎的调和级数，它近似等于$\ln n + \gamma$，在分析时间复杂度时，可以认为它就是$O(\log n)$，所以这段代码的时间复杂度就是$O(n \log n)$

$O(n^2)$

int x = 0,n = 100000;
for (int i = 1;i <= n;i++) 
{
    for (int j = i;j <= n;j++) 
    {
        x++;
    }
}

i等于1时，j从1到n，执行n次；
i等于2时，j从2到n，执行n - 1次；
i等于3时，j从3到n，执行n - 2次；
…
i等于n时，j从n到n，执行1次。
总执行次数为$\sum_{i=1}^{n} i$，即$\frac{n*(n + 1)}{2}$次，时间复杂度$O(n^2)$。

$O(2^n)$

int n = 20,x = 0;
for (int i = 0;i < (1 << n);i++)  
{
    x++;
}

注：1 << n,表示$2 ^ n$
执行次数$2^n$,时间复杂度$O(2^n)$。

3. 分析时间复杂度的作用

一般来说，我们估计一秒能执行大约$10^8$次运算，从而我们能根据题目给定的数据范围来估计要用什么算法

数据范围	允许的时间复杂度	适用算法举例
$n \le 10$	$O(n!)$ 或 $O(C^n)$	回溯、暴力搜索
$n \le 20$	$O(2^n)$	状态压缩 DP
$n \le 40$	$O(2^{n/2})$	折半枚举
$n \le 10^2$	$O(n^3)$	三重循环的 DP、Floyd
$n \le 10^3$	$O(n^2)$	二重循环的 DP、背包
$n \le 10^5$	$O(n\log n)$	大多数题目都是这个范围，所以各类算法都有
$n \le 10^6$	$O(n)$	线性 DP、滑动窗口
$n \le 10^9$	$O(\sqrt n)$	判断质数
$n \le 10^{18}$	$O(\log n)$ 或 $O(1)$	二分、快速幂、数学公式

注：实际做题时还要考虑常数的影响，如果你遇到了TLE(Time Limit Exceed)，优先考虑是否是时间复杂度分析错误，进而想是否是常数太大。

空间复杂度

1. 什么是空间复杂度

与时间复杂度基本一致，不同的是，它考察的是算法在运算中额外占用的存储空间大小。
注：不包含原始输入数据的内存，只统计算法新增的临时空间、变量、数组、递归栈等开销。

2. 常见空间复杂度

O(1)

int x;
cin >> x;//题目输入数据，不计入空间复杂度分析
int tmp = x;
printf("%d",tmp);

创见一个变量，空间复杂度$O(1)$。

$O(n)$

void dfs(int i) 
{
    if (i == n) return ;
    def(i + 1);
}

递归深度n，空间复杂度$O(n)$。

$O(2^n)$

int n = 20;
//题目输入数据，不计入空间复杂度分析
vector<int> a(n);
for (int i = 0;i < n;i++) cin >> a[i];
vector<int> dp(1 << n);

创见$2^n$个变量,空间复杂度$O(2^n)$。

3. 分析空间复杂度的作用

一般情况下，题目不会卡你空间，以256MB算，一个int 4B，可以创建$6.7 \times 10^7$ 个int变量。