一 概念

时间复杂度描述算法执行时间随问题规模n增大而变化的趋势,是关于n的渐近函数。算法执行时间通常由语句频度(某条语句的执行次数)来衡量。设算法中所有语句的频度之和为T(n),它是问题规模n的函数。当n足够大时,低阶项和常数系数对整体增长趋势的影响可以忽略不计,因此只需关注T(n)中增长最快的项。这一项通常由算法中的基本运算(关键语句)的执行次数决定,该执行次数的数量级即为整个算法的时间复杂度。

时间复杂度通常用大O记号表示:若存在正常数C和n₀，使得对所有n≥n₀时,都有$0 \leq T(n) \leq C f(n)$，则称T(n)=O(f(n))，它表示当n足够大时,T(n)的增长速度不超过f(n)的常数倍。

e.g：$T(n) = 3n^2 + 100n + 5 \to O(n^2)$

二 加法原则与乘法原则

2.1 加法原则

如果两段代码按顺序执行，则总时间复杂度为两者中的高阶项，判断方法看阶次

即：$O(f(n)) + O(g(n)) = O(\max\{f(n), g(n)\})$

e.g:

void example1(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", i + j);
        }
    }//第一段
    for (int k = 0; k < n; k++) {
        printf("%d ", k);
    }
}//第二段

其中，第一段代码的时间复杂度为$O(n^2)$，第二段的时间复杂度为$O(n)$，则$O(n^2)+O(n)=O(n^2)$，故这个example1函数的时间复杂度为$O(n^2)$

2.2 乘法原则

如果有一段代码嵌套在另一段的内部，则总时间复杂度为两者乘积

即：$O(f(n)) \cdot O(g(n)) = O(f(n) \cdot g(n))$

e.g

void demo(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", i + j);
        }
    }
}

其中，外层循环的时间复杂度为O(n)，内层循环的时间复杂度为$O(n)$，根据乘法原则，这段代码的时间复杂度为$O(n)\cdot O(n)=O(n^2)$

三 时间复杂度的阶次

根据这个，在加法原则中，就可以判断哪个阶次高，从而解出正确的时间复杂度

四 时间复杂度的求法

4.1 普通代码的时间复杂度

e.g

void func(int n) {
    int a = 10;
    int b = 20;
    int c = a + b;
}

这段代码里面未包含任何循环，故其时间复杂度必然为O(1)

4.2 while循环时间复杂度的求法

对于while循环求时间复杂度，我们可以利用设t法，列出表格解出t，则t即为时间复杂度

t	1	2	……	t
x

e.g

void fun(int n) {
int i = 1;
while (i <= n) {
i = i * 2;//关键语句
}
}

此时，我们可以设关键语句运行时间为t，即设i=i*2运行了t次，则可以列出表格

t	1	2	3	……	t
i	2	4	8	……	$2^{t}$

当$2^{t}>n$的时候，跳出循环，解得t>$\log_2 n$，故这段代码的时间复杂度为$O(\log_2 n)$

4.3 for循环时间复杂度的求法

4.3.1 普通循环

e.g.1

void test(int n){
    int x = 10;
    for(int i=0; i<10; i++){
        x++;
    }
}

此时n小于10，代表只会循环十次，故这段的时间复杂度为O(1)

e.g.2

void test1(int n) {
    for (int i = 0; i < n; i++) {
        printf("hello");
    }
}

这个循环中，i=0，故会循环n次，故这段代码的时间复杂度为$O(n)$

4.3.2 嵌套循环

对于嵌套循环，也可以使用表格法，来进行解决，最后对内循环次目进行求和即可

外循环次数
循环条件
i取值
内循环次目

e.g.1

for(int i = n-1; i >= 2; i--){
    for(int j = 1; j < i; j++){  
        if(A[j] > A[j+1]){
            int temp = A[j];
            A[j] = A[j+1];
            A[j+1] = temp;
        }
    }
}

遇到嵌套循环，首先要先判断变量有跟循环有直接关系，如果有，再列表格

这里很明显有，所以直接列表格即可

外循环次数	1	2	3	……	t
循环条件	n-1	n-2	n-3	……	1
i取值	n-1	n-2	n-3	……	1
内循环次目	n-2 (j<i,i=n-1,故为n-2)	n-3	n-4	……	0

当t<1时，循环跳出，此时可以知道，t=1为最后一次循环值，那么的话就可以对内循环次目进行求和了

此时$\sum_{i=1}^{n-2} i$=$\sum_{i=1}^{n-2} i = \frac{(n-2)(n-2+1)}{2} = \frac{(n-2)(n-1)}{2}$

由于时间复杂度只看最高项，故这时候我们可以直接忽略掉其他项和最高项前面的系数，只看最高项，为$n^2$,故时间复杂度为O($n^2$)

e.g.2

求下列代码的时间复杂度

	int count = 0;
	for (int k = 1; k <= n; k *= 2) {
		for (int j = 1; j <= n; j++) {
			count++;
		}
	}

首先先判断内层循环是否跟外层的i值有关系，很明显没有，故接下来直接列表格即可

外循环次数	1	2	3	……	t
循环条件	1	2	4	……	$2^{t-1}$
i取值	1	2	4	……	$2^{t-1}$
内循环次目	n	n	n	……	n

此时当$2^{t-1}>n$，即t>$\log_2 (n-1)$，跳出循环，此时对内循环次目进行求和，由于都是n，一共有$\log_2 (n-1)$项，所以最后为n$\log_2 (n-1)$=$n\log_2 n$–$n$，根据加法原理，故最后的时间复杂度为$O(n\log_2 n)$

五 王道书时间复杂度练习解答

这一段将为王道书上时间复杂度那块进行解析

7.

求下列代码的时间复杂度

void fun(int n) {
    int i = 0;
    while (i * i * i <= n)
        i++;
}

这一题考的是while循环的时间复杂度求法，利用设t法来解就可以了

9.求下列代码段的时间复杂度

if (n >= 0) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            printf("输入数据大于或等于零\n");
} else {
    for (int j = 0; j < n; j++)
        printf("输入数据小于零\n");
}

这题考的是嵌套for循环和加法原理，第一个很明显时间复杂度为$O(n^2)$,下面这个很明显是$O(n)$,那么利用加法原理就可以知道时间复杂度为$O(n^2)$

10.求下列代码的运行次数

int m = 0, i, j;
for (i = 1; i <= n; i++)
    for (j = 1; j <= 2 * i; j++)
        m++; 

注意到它考的是运行次数，那么的话只需要把最后的求和给求出来就可以了

11.求下列代码的时间复杂度

int Func(int n) {
    if (n == 1)
        return 1;
    else
        return 2 * Func(n / 2) + n;
}

这道题考到了一个递归函数时间复杂度的求法，对于这类题，关注它的关键语句就可以了，注意到一个是$n/2$，那么后面就是对n进行一个赋值，故我们就可以把这个语句转换为n=(n/2)进行一个循环，利用设t法来解即可

12.求下列代码的时间复杂度

x = 2;
while (x < n / 2)
    x = 2 * x;

这个的话直接用设t法来解就可以了

13.求下列代码的时间复杂度

int fact(int n) {
    if (n <= 1)
        return 1;
    return n * fact(n - 1);
}

还是递归函数的时间复杂度，找到关键语句，注意到是把n变成n-1，那么这个语句就可以变成n=n-1，转换成一个while循环，即可求出答案

15.求下列代码的时间复杂度（2017年统考真题）

int func(int n) {
    int i = 0, sum = 0;
    while (sum < n)
        sum += ++i;
    return i;
}

这也是一个while循环的时间复杂度，用设t法就可以解决了

16.求下列代码的时间复杂度（2019年统考真题）

x = 0;
while (n >= (x + 1) * (x + 1))
    x = x + 1;

还是用设t法即可迅速解决

17.求下列代码的时间复杂度

int sum = 0;
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < i; j++)
        sum++;

这是一个嵌套for循环，观察到内层寻跟外层循环有关系，故我们需要列表解决（2022年真题）

18.求下列代码的时间复杂度

int count = 0, i, j;
for (i = 1; i * i <= n; i++)
    for (j = 1; j <= i; j++)
        count++;

这题也是嵌套for循环，直接用表格法即可解决

这里需要补充一个平方和公式：$\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$

六 总结

这里面总结了绝大多数时间复杂度问题问题一个解法，对于递归求解篇幅较小，有时间的话会补充。