YiNotes

时间复杂度

Jun 19, 20251 min read

408高频考点：时间复杂度

1 单层循环

1.1 线性时间复杂度

for 循环：

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

while 循环：

int x = 0;
int i = 0;
while (i < n){
    ++x;
    ++i;
}

时间复杂度 。

1.2 对数时间复杂度

for 循环：

int x = 0;
for (int i = 1; i < n; i *= 2) {
    ++x;
}

while 循环：

int x = 0;
int i = 1;
while (i < n){
    ++x;
    i *= 2;
}

时间复杂度 。

1.3 方根时间复杂度

for 循环：

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

while 循环：

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

时间复杂度 。

2 多层循环

2.1 嵌套循环指针无关

j 指针与 i 指针无关：

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

时间复杂度 。

j 指针与 i 指针无关：

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

时间复杂度 。

j 指针与 i 指针无关：

int x = 0;
for (int i = 0; i * i < n; ++i) {
    for (int j = 0; j * j < n; ++j) {
        ++x;
    }
}

时间复杂度 。

2.2 嵌套循环指针相关

j 指针与 i 指针相关：

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

时间复杂度 。

严格计算如下：

j 指针与 i 指针相关：

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

时间复杂度 。

严格计算如下：

j 指针与 i 指针相关：

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

时间复杂度 。

严格计算如下：

根据斯特林近似公式：

j 指针与 i 指针相关：

int x = 0;
for (int i = 0; i * i < n; ++i) {
    for (int j = 0; j * j < i; ++j) {
        ++x;
    }
}

时间复杂度 。

严格计算如下：

根据柯西不等式：

j 指针与 i 指针相关：

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

时间复杂度 。

用定义法求解，用 表示执行的轮次，严格计算如下：

2.3 嵌套循环指针总结

⑴ j 指针与 i 指针无关时，时间复杂度直接相乘。

例如形如

int x = 0;
for (int i = 0; f(i) < n; ++i) {
    for (int j = 0; g(j) < n; ++j) {
        ++x;
    }
}

时间复杂度为 。

⑵ j 指针与 i 指针相关时，如果两个指针均为每次自增，j 为 i 的复合函数，再相乘。

例如形如

int x = 0;
for (int i = 0; f(i) < n; ++i) {
    for (int j = 0; g(j) < i; ++j) {
        ++x;
    }
}

时间复杂度为 。

⑶ j 指针与 i 指针相关时，如果两个指针变化非线性，用定义法计算。

3 时间复杂度排序

从小到大排序如下：

4 历年真题

2011 年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题第 1 题：

下列程序段的时间复杂度是（ ）。

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

A.

B.

C.

D.

解答：本题为单层循环类型题，很明显选 A。

2014 年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题第 1 题：

下列程序段的时间复杂度是（ ）。

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

A.

B.

C.

D.

解答：本题为多层循环中嵌套循环指针无关类型题，很明显选 C。

2022 年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题第 1 题：

下列程序段的时间复杂度是（ ）。

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

A.

B.

C.

D.

解答：

方法一：定义法

本题为多层循环中嵌套循环指针相关类型题，且指针变化非线性，所以只能用定义法求解，程序主要代价为 sum++，这里统计 sum++ 的执行次数，用 表示外层循环的执行轮次，设 的最大值为 ，则

对于外层循环的 ：

第一次迭代有 ；

第 次迭代有 ；

最后一次迭代有 ，即 为满足 的最大整数，所以 ，此时 。

对于内层循环的 ：

第一次迭代有 ；

最后一次迭代有 。

综上，推出如下计算式：

本题选 B。

由于这里用到了不等式运算，所以涉及 的定义：描述渐近上界，给定函数 , 。

一般书写为 ，计算可转化为 。

同时涉及取整符号性质：

注：参考《算法导论》相关章节如下：

方法二：枚举

对于没有学习过算法导论的同学来说，方法一显然超纲了，但是并非没有办法，我们可以枚举

显然有

这道题难度非常大，只能用定义法。归根结底基础还是要打扎实，用定义法求解永远不会出错。

Link to original

Graph View

Backlinks