Big O
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 次,所以时间复杂度为 。
3. 分步累加问题
考虑以下代码片段:
for (int i = 1; i <= n; i *= 2) {
printf("%d ", i);
}
请问上述代码的时间复杂度是多少?
Answer 3
循环每次都使 i
的值翻倍,因此它将在 log(n) 步之后完成。所以时间复杂度为 。
代码片段中的循环语句执行了一段以 2 为基数的指数增长的逻辑。也就是说,每次循环结束后,i 的值会翻倍。
让我们来列出几次迭代的 i 的值,以便更好地理解其行为:
- 第1次迭代: i = 1
- 第2次迭代: i = 2
- 第3次迭代: i = 4
- 第4次迭代: i = 8
- 第5次迭代: i = 16
...
...
这是一个指数增长,每次都乘以 2。
为了得到循环的次数,考虑这样的情形:当循环执行 k 次之后,i 的值是 ()。我们知道当 (i > n) 时,循环停止。因此,我们可以得到:
()
对两边取对数:
()
所以,k(即循环的次数)是 。
因此,这个代码片段的时间复杂度是 ()。
这是一个很好的问题。很多人初看循环条件时,可能会觉得这是一个直到 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
翻倍时,所需的操作数也翻倍。
因此,循环的时间复杂度为 (),而不是 ()。
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
外层循环为 ,内层循环为 ,所以时间复杂度为 。
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。这意味着它将在 次调用后达到 1 或更小的值。
因此,我们可以将这个函数的时间复杂度描述为()。
所以,function(n)
的时间复杂度是 ()。
7. 多个连续循环问题
考虑以下代码片段:
for (int i = 0; i < n; i++) {
printf("%d ", i);
}
for (int j = 0; j < m; j++) {
printf("%d ", j);
}
请问上述代码的时间复杂度是多少?
Answer 7
第一个循环的时间复杂度为 ,第二个循环的时间复杂度为 。当你有顺序执行的语句时,你将它们的复杂度相加。所以总时间复杂度为 。
8. 复杂嵌套循环问题
考虑以下代码片段:
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
printf("%d, %d ", i, j);
}
}
请问上述代码的时间复杂度是多少?
Answer 8
内循环的次数随着外循环的迭代而减少。当 时,内部循环将执行 n 次;当 时,执行 次;依此类推。因此,总的运行次数为 ,这是一个算术级数。所以时间复杂度为 ,但常数和低次项在大 O 符号表示中被省略,因此答案是 。
我为你详细解释一下:
当我们计算序列 () 的和时,我们得到的是一个等差数列的和。这个和可以通过以下公式得到:
现在我们来分析这个公式:
乘以 () 不会改变其时间复杂度,因为在大 O 表示法中,我们忽略了常数因子。
因此,我们的焦点应该是 ()。
这基本上是 (),其中 () 是主导项,而 (n) 在面对大的输入时相对较小。
因此,我们通常忽略次要项并保留主导项,即 (),这给出了时间复杂度 。
9. 递归计算问题
考虑以下函数:
int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
请问fibonacci(n)
的时间复杂度是多少?
Answer 9
此函数是计算斐波那契数列的经典方法,但它的效率很低。它为每一个 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 次,所以时间复杂度为 。
11. 单一循环问题
考虑以下代码片段:
for (int i = 0; i < n; i++) {
printf("%d ", i);
}
请问上述代码的时间复杂度是多少?
Answer 11
个简单的遍历,时间复杂度为 。
12. 连续循环问题
考虑以下代码片段:
for (int i = 0; i < n; i++) {
printf("%d ", i);
}
for (int j = 0; j < n; j++) {
printf("%d ", j);
}
请问上述代码的时间复杂度是多少?
Answer 12
两个连续的遍历,每个都是 ,所以时间复杂度为 。但在大 O 符号表示中,我们不考虑常数倍数,所以答案为 。
13. 基本嵌套循环问题
考虑以下代码片段:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d, %d ", i, j);
}
}
请问上述代码的时间复杂度是多少?
请问上述代码的时间复杂度是多少?
Answer 13
外层循环 次,每次内层循环也是O(n)次,所以时间复杂度为 。
14. 不等步长的循环问题
考虑以下代码片段:
for (int i = 1; i <= n; i *= 3) {
printf("%d ", i);
}
请问上述代码的时间复杂度是多少?
Answer 14
循环每次使 i
的值乘以 3,它将在 步之后完成。所以时间复杂度为 。但底数在时间复杂度中通常不被考虑,所以简化为 。
15. 嵌套与不等步长问题
考虑以下代码片段:
for (int i = 0; i < n; i++) {
for (int j = 1; j <= n; j *= 2) {
printf("%d, %d ", i, j);
}
}
请问上述代码的时间复杂度是多少?
Answer 15
外层循环为 ,内层循环为 (因为每次j都翻倍),所以时间复杂度为 。
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
三个嵌套的循环,每个都是 次,所以时间复杂度为 。
17. 递归问题
考虑以下函数:
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
请问 factorial(n)
的时间复杂度是多少?
Answer 17
该函数每次递归时,n 都减少 1。它将在 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
每次函数调用都将问题规模减半,并产生两个子问题。使用递归树或主方法,可以得到时间复杂度为 。
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
外层循环为 ,然后递归地处理规模减半的问题。这个结构很像二叉树,其中每层的工作量是 。所以时间复杂度为 。
20. 斐波那契递归问题
考虑以下函数:
int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
请问 fibonacci(n)
的时间复杂度是多少?
Answer 20
此函数为每个 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;
}
答案:
for(int i=0; i*i<n; i++)
这个循环会运行直到 () 大于或等于 n。考虑到 i 的平方增长速度比 i 本身快,这意味着循环会运行直到 i 接近于 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 的值都会翻倍,循环的时间复杂度近似为
为什么是 ?
因为,我们不是问 “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(n√n)
。
公众号:AI悦创【二维码】
AI悦创·编程一对一
AI悦创·推出辅导班啦,包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发、Web、Linux」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然,还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线,随时响应!微信:Jiabcdefh
C++ 信息奥赛题解,长期更新!长期招收一对一中小学信息奥赛集训,莆田、厦门地区有机会线下上门,其他地区线上。微信:Jiabcdefh
方法一:QQ
方法二:微信:Jiabcdefh
- 0
- 0
- 0
- 0
- 0
- 0