Big O

AI悦创原创大约 13 分钟...约 4020 字

1. 数组遍历问题

考虑以下代码片段：

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

请问上述代码的时间复杂度是多少？

Answer 1

代码是对长度为 n 的数组进行简单的遍历，只有一个循环，所以时间复杂度为 O(n)。

2. 嵌套循环问题

考虑以下代码片段：

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

请问上述代码的时间复杂度是多少？

Answer 2

外层循环和内层循环都是 n 次，所以时间复杂度为 $O(n^2)$ 。

3. 分步累加问题

考虑以下代码片段：

for (int i = 1; i <= n; i *= 2) {
    printf("%d ", i);
}

请问上述代码的时间复杂度是多少？

Answer 3

循环每次都使 i 的值翻倍，因此它将在 log(n) 步之后完成。所以时间复杂度为 $O(log n)$ 。

代码片段中的循环语句执行了一段以 2 为基数的指数增长的逻辑。也就是说，每次循环结束后，i 的值会翻倍。

让我们来列出几次迭代的 i 的值，以便更好地理解其行为：

第1次迭代: i = 1
第2次迭代: i = 2
第3次迭代: i = 4
第4次迭代: i = 8
第5次迭代: i = 16
...
...

这是一个指数增长，每次都乘以 2。

为了得到循环的次数，考虑这样的情形：当循环执行 k 次之后，i 的值是 ( $2^k$ )。我们知道当 (i > n) 时，循环停止。因此，我们可以得到：

( $2^k > n$ )

对两边取对数：

( $k > \log_2 n$ )

所以，k（即循环的次数）是 $O(log n)$ 。

因此，这个代码片段的时间复杂度是 ( $O(\log n)$ )。

为什么不是 O(n)?

这是一个很好的问题。很多人初看循环条件时，可能会觉得这是一个直到 n 的循环，所以时间复杂度是 ( $O(n)$ )。但我们需要深入分析循环的真正行为。

首先，这个循环不是每次都增加一个固定的数值（例如 i++），而是每次都将 i 的值翻倍（i *= 2）。这意味着 i 的增长是以指数的方式，而不是线性的方式。

简单地说，假设 n = 16：

第1次迭代: i = 1
第2次迭代: i = 2
第3次迭代: i = 4
第4次迭代: i = 8
第5次迭代: i = 16
只需要5次迭代就可以达到16。

现在，假设 n 翻倍，即 n = 32：

第1次迭代: i = 1
第2次迭代: i = 2
第3次迭代: i = 4
第4次迭代: i = 8
第5次迭代: i = 16
第6次迭代: i = 32
这次只需要6次迭代。

当 n 翻倍时，迭代次数仅仅增加了1。这与线性的关系 (O(n)) 不同，其中当 n 翻倍时，所需的操作数也翻倍。

因此，循环的时间复杂度为 ( $O(\log n)$ )，而不是 ( $O(n)$ )。

4. 不连续循环问题

考虑以下代码片段：

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

请问上述代码的时间复杂度是多少？

Answer 4

这是一个简单的不连续循环问题。

代码片段的核心部分是这个 for 循环：

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

循环的特点是每次迭代，循环变量 i 增加 2。因此，这个循环将执行 n/2 次。例如，当 n = 10 时，输出将是 0 2 4 6 8。

所以，总的来说，这个 for 循环的迭代次数是 n/2。但当我们讨论时间复杂度时，我们通常只关心最高阶的项并且省略掉常数倍。因此，尽管循环执行了n/2次，时间复杂度仍然是O(n)。

答案是：该代码片段的时间复杂度为 O(n)。

5. 嵌套与分步问题

考虑以下代码片段：

for (int i = 0; i < n; i++) {
    for (int j = 1; j <= n; j *= 2) {
        printf("%d, %d ", i, j);
    }
}

请问上述代码的时间复杂度是多少？

Answer 5

外层循环为 $O(n)$ ，内层循环为 $O(log n)$ ，所以时间复杂度为 $O(n log n)$ 。

6. 函数调用问题

考虑以下函数：

void function(int n) {
    if (n <= 1) return;
    printf("%d ", n);
    function(n/2);
}

当我们调用function(n)时，时间复杂度是多少？

Answer 6

为了理解函数 function 的时间复杂度，我们可以考虑它如何工作。

当我们调用 function(n)，它首先检查 n 是否小于等于1，如果是，函数直接返回，没有额外的操作。如果不是，函数会打印出 n 的值，然后再次调用自己，但这次参数是 n/2。

每次函数被调用时，它处理的数字都会除以 2。这意味着它将在 $log_2(n)$ 次调用后达到 1 或更小的值。

因此，我们可以将这个函数的时间复杂度描述为( $O(\log n)$ )。

所以，function(n) 的时间复杂度是 ( $O(\log n)$ )。

7. 多个连续循环问题

考虑以下代码片段：

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

请问上述代码的时间复杂度是多少？

Answer 7

第一个循环的时间复杂度为 $O(n)$ ，第二个循环的时间复杂度为 $O(m)$ 。当你有顺序执行的语句时，你将它们的复杂度相加。所以总时间复杂度为 $O(n + m)$ 。

8. 复杂嵌套循环问题

考虑以下代码片段：

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

请问上述代码的时间复杂度是多少？

Answer 8

内循环的次数随着外循环的迭代而减少。当 $i = 0$ 时，内部循环将执行 n 次；当 $i = 1$ 时，执行 $n-1$ 次；依此类推。因此，总的运行次数为 $n + (n-1) + (n-2) + ... + 1$ ，这是一个算术级数。所以时间复杂度为 $O(n^2/2)$ ，但常数和低次项在大 O 符号表示中被省略，因此答案是 $O(n^2)$ 。

我为你详细解释一下：

当我们计算序列 ( $n + (n-1) + (n-2) + \dots + 1$ ) 的和时，我们得到的是一个等差数列的和。这个和可以通过以下公式得到：

$\text{和} = \frac{n(n + 1)}{2}$

现在我们来分析这个公式：

乘以 ( $\frac{1}{2}$ ) 不会改变其时间复杂度，因为在大 O 表示法中，我们忽略了常数因子。

因此，我们的焦点应该是 ( $n(n + 1)$ )。

这基本上是 ( $n^2 + n$ )，其中 ( $n^2$ ) 是主导项，而 (n) 在面对大的输入时相对较小。

因此，我们通常忽略次要项并保留主导项，即 ( $n^2$ )，这给出了时间复杂度 $O(n^2)$ 。

9. 递归计算问题

考虑以下函数：

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

请问fibonacci(n)的时间复杂度是多少？

Answer 9

此函数是计算斐波那契数列的经典方法，但它的效率很低。它为每一个 n 都生成了两个递归调用（除了基本情况）。因此时间复杂度近似于 $O(2^n)$ 。

11. 矩阵遍历问题

考虑以下代码片段：

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

请问上述代码的时间复杂度是多少？

Answer 10

外层循环运行 n 次，内层循环运行 m 次，所以时间复杂度为 $O(n * m)$ 。

11. 单一循环问题

考虑以下代码片段：

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

请问上述代码的时间复杂度是多少？

Answer 11

个简单的遍历，时间复杂度为 $O(n)$ 。

12. 连续循环问题

考虑以下代码片段：

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

请问上述代码的时间复杂度是多少？

Answer 12

两个连续的遍历，每个都是 $O(n)$ ，所以时间复杂度为 $O(2n)$ 。但在大 O 符号表示中，我们不考虑常数倍数，所以答案为 $O(n)$ 。

13. 基本嵌套循环问题

考虑以下代码片段：

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

请问上述代码的时间复杂度是多少？

Answer 13

外层循环 $O(n)$ 次，每次内层循环也是O(n)次，所以时间复杂度为 $O(n^2)$ 。

14. 不等步长的循环问题

考虑以下代码片段：

for (int i = 1; i <= n; i *= 3) {
    printf("%d ", i);
}

请问上述代码的时间复杂度是多少？

Answer 14

循环每次使 i 的值乘以 3，它将在 $log_3(n)$ 步之后完成。所以时间复杂度为 $O(log_3 n)$ 。但底数在时间复杂度中通常不被考虑，所以简化为 $O(log n)$ 。

15. 嵌套与不等步长问题

考虑以下代码片段：

for (int i = 0; i < n; i++) {
    for (int j = 1; j <= n; j *= 2) {
        printf("%d, %d ", i, j);
    }
}

请问上述代码的时间复杂度是多少？

Answer 15

外层循环为 $O(n)$ ，内层循环为 $O(log n)$ （因为每次j都翻倍），所以时间复杂度为 $O(n log n)$ 。

16. 三重循环问题

考虑以下代码片段：

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

请问上述代码的时间复杂度是多少？

Answer 16

三个嵌套的循环，每个都是 $O(n)$ 次，所以时间复杂度为 $O(n^3)$ 。

17. 递归问题

考虑以下函数：

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

请问 factorial(n) 的时间复杂度是多少？

Answer 17

该函数每次递归时，n 都减少 1。它将在 n 步之后完成。因此，时间复杂度为 $O(n)$ 。

18. 分治递归问题

考虑以下函数：

void divideAndConquer(int arr[], int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    divideAndConquer(arr, l, mid);
    divideAndConquer(arr, mid + 1, r);
}

请问上述代码的时间复杂度是多少？

Answer 18

每次函数调用都将问题规模减半，并产生两个子问题。使用递归树或主方法，可以得到时间复杂度为 $O(n log n)$ 。

19. 递归加循环问题

考虑以下函数：

void recursiveLoop(int n) {
    if (n <= 0) return;
    for (int i = 0; i < n; i++) {
        printf("%d ", i);
    }
    recursiveLoop(n/2);
}

请问 recursiveLoop(n) 的时间复杂度是多少？

Answer 19

外层循环为 $O(n)$ ，然后递归地处理规模减半的问题。这个结构很像二叉树，其中每层的工作量是 $O(n)$ 。所以时间复杂度为 $O(n log n)$ 。

20. 斐波那契递归问题

考虑以下函数：

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

请问 fibonacci(n) 的时间复杂度是多少？

Answer 20

此函数为每个 n 生成两个递归调用。其效率非常低，时间复杂度近似于 $O(2^n)$ 。

for(int i=0;i<n*n;i++)
for(int I=0;i*i<n;i++)
for(int l=0;k<n;K*K)
for(int k=0;k<n;k=k*k)

Question 1

下面代码的时间复杂度：

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

在解决这个题目时，思考下面的代码循环几次：

#include <stdio.h>


int main(void) {
    for (int i=0; i < 10*10; i++) {
        printf("%d", i);
    }
    return 0;
}

答案：

$O(n^2)$

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

这个循环会运行直到 ( $i^2$ ) 大于或等于 n。考虑到 i 的平方增长速度比 i 本身快，这意味着循环会运行直到 i 接近于 n 的平方根。因此，循环将执行大约 ( $\sqrt{n}$ ) 次。所以时间复杂度为 ( $O(\sqrt{n})$ )

Question 2

下面代码的时间复杂度：

for(int k=2;k<n;k=k*k)

这个循环的特点是每次迭代后 k 的值都会被更新为它的平方。

从 k = 2 开始：

第一次迭代：k = 2，之后 k 更新为 k * k = 4;
第二次迭代：k = 4，然后 k 更新为 k * k = 16;
第三次迭代：k = 16，然后 k 更新为 k * k = 256
......

我们可以看到，k 的值增长的非常快。更具体的说：每次迭代后，k 的值都会成为之前的平方。

因此，循环的迭代次数与 n 的对数有关，但是基数不是 2，而是一个更大的数。

我们为了确定具体执行了多少次，我们可以考虑这样一个问题：多少次的平方操作会使一个数超过 n？或者 2 的什么次方会超过 n？

这和我们常规的对数是不一样的，但是与对数相关。考虑到每次迭代 k 的值都会翻倍，循环的时间复杂度近似为 $O(log log n)$

为什么是 $O(log log n)$ ？

因为，我们不是问 “2 的多少次方会得到 n”

Question 3

#include <stdio.h>

int main() {
    for (int i = 1; i *i < n; i++) {
        for (int j = 1; i <= n; j++) {
            printf("   ");
        }
        for (int k = 1; k * k < n; k++) {
            printf("   ");
        }
    }
    return 0;
}

我们首先要分析每个循环的时间复杂度，并然后将它们组合在一起。

第一个外部循环：for (int i = 1; i * i < n; i++)

这个循环的次数是 sqrt(n) 次，因为 i*i < n，所以 i 大约是从 1 到 sqrt(n)。

第一个内部循环：for (int j = 1; i <= n; j++)

注意这里应该有一个小错误。这个循环应该是基于 j 的条件，而不是 i，如果是i的话这个循环实际上并不会根据i的值有任何变化，会导致一个无限循环（因为 i 在这个循环内部并不改变）。如果我们修正这个错误，假设为：for (int j = 1; j <= n; j++)，那么这个循环会运行n次。

第二个内部循环：for (int k = 1; k * k < n; k++)

与第一个外部循环类似，这个循环也会运行 sqrt(n) 次。

现在，结合这些循环：

对于外部循环的每次迭代，第一个内部循环会运行 n 次，第二个内部循环会运行 sqrt(n) 次，所以一次外部循环迭代的复杂度是 n + sqrt(n)。

因此，总时间复杂度是：
( $O(\sqrt{n} * (n + \sqrt{n})) = O(n\sqrt{n} + n)$ )

当我们关注高阶项时，时间复杂度可以简化为：O(n√n)。

公众号：AI悦创【二维码】

AI悦创·编程一对一

AI悦创·推出辅导班啦，包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Web、Linux」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然，还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线，随时响应！微信：Jiabcdefh

C++ 信息奥赛题解，长期更新！长期招收一对一中小学信息奥赛集训，莆田、厦门地区有机会线下上门，其他地区线上。微信：Jiabcdefh

方法一：QQopen in new window

方法二：微信：Jiabcdefh