关于复杂度计算的问题
波波老师今天被同问问了几个关于复杂度的问题，我发现我最后给的答案错了，您可以帮我分析下嘛，谢谢老师！
//1.我给的是O(nlogn)->和老师答案匹配
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j *= 2){}
//我给的是O(nlogn),外层O(logn),内层O(n) ->错误，老师给的是O（n）
for (int i = 0; i < n; i *= 2)
for (int j = 0; j < i; j ++){}
//然后我就陷入了疑惑，然后又想了如下几个我本来要判断O(nlogn)的例子，但是现在根据这题的理解
//又改为O（n）的情况
int sum = 0;
for (int n = N; n > 0; n /= 2)
for(int i = 0; i < n; i++)
sum++;
int sum = 0;
for (int i = 1 i < N; i *= 2)
for (int j = 0; j < i; j++)
sum++;波波老师请问我判断O(nlogn)有错么，要是有错的话，我分别考虑2个循环的最极端条件有错么？
我有个想法就是，复杂度有上界和下界，是不是入股哦一个复杂度我们可以更加精确的话，那么他的复杂度就是那个更精确的那个呢？
31
收起
正在回答 回答被采纳积分+1
3回答
v不离不弃v
2020-09-09 03:06:34
老师我明白啦！！！
第一个和第二个示例是相同的（就时间复杂度而言）。对于他们来说，时间复杂度为O（N）。为什么。让我们计算一下。对于第一个示例，您的内部循环运行N次，然后运行N / 2次，然后运行N / 4并上升到1。因此，时间复杂度为O（N + N / 2 + N / 4 + .. + 1 ），此GP的总和为（2n-1）。因此，第一种情况的时间复杂度为 O（N）。
对于第二个示例，您的内部循环运行1次，然后运行2次，运行4次，直至达到N。因此，时间复杂度为O（1 + 2 + 4 + ... + N）和该GP的值为2 log（N + 1） -1，它等于N。因此，第二种情况的时间复杂度也是 O（N）。
对于
for(int i = 0; i < n; i ++) for(int j = 0; j < i; j ++)
内层循环依靠外层，则一共进行1 + 2+3 + 4+ ......n = n（n + 1）/2 = O(n^2)
相似问题
如何实现空间复杂度O(1)的快排
20
0
3
可以这样来看双路快速排序的算法复杂度吗
30
0
3
Leetcode 809 时间复杂度
9
1
4
归并排序法的复杂度计算
3
0
1
不认同老师说复杂度分析里的常数系数是没有意义的
53
2
8
登录后可查看更多问答，登录/注册
恭喜解决一个难题，获得1积分~
来为老师/同学的回答评分吧
0 星