关于复杂度计算的问题

来源：1-10 均摊复杂度和防止复杂度的震荡

v不离不弃v

2020-09-09 02:35:23

波波老师今天被同问问了几个关于复杂度的问题，我发现我最后给的答案错了，您可以帮我分析下嘛，谢谢老师！

//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个循环的最极端条件有错么？

我有个想法就是，复杂度有上界和下界，是不是入股哦一个复杂度我们可以更加精确的话，那么他的复杂度就是那个更精确的那个呢？

写回答

3回答

v不离不弃v

提问者

2020-09-09

老师我明白啦！！！

第一个和第二个示例是相同的（就时间复杂度而言）。对于他们来说，时间复杂度为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)

hiuyubobobo

h 赞！你的方法非常对，对于时间复杂度，更严谨的分析，需要把循环里每一次执行加起来，得到的结果是一个级数。所以大多数时间复杂度的问题本质都是级数求和。值得一提的是，对于你的 2，严格从数学的角度讲，说他的的复杂度是 O(nlogn) 是正确的，但是说 O(n) 也是正确的。因为大 O 符号本身就表示上界。只不过，在这个例子中，O(n) 是一个比 O(nlogn) 更紧的上界。我们一般都更关注那个更紧的上界。在这个课程中，对于堆的 heapify 操作的时间复杂度分析，有异曲同工的地方，学到那里可以再关注一下。再 btw，一般软件开发岗面试应该不会过于纠缠这种复杂度的计算的。加油！：）

h020-09-09

共1条回复

v不离不弃v

提问者

2020-09-09

对于

for (int i = 0; i < n; i++) //O( n )
    for (int j = 1; j < i; j*=2) //O（logn）

他的复杂度是小于O（nlogn）的，但是我们考虑最坏情况所以是O（nlogn）

但是对于

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

可否理解为，内层循环依赖于外层，计算的时候就不能这么笼统的分层分别计算了呢？

但是，第一个例子的内层循环也是依赖于外层循环的呀？有点不明白

v不离不弃v

提问者

2020-09-09

郁闷，例子给重复了，为啥现在不能重新编辑了呢，难受。。。。

算法与数据结构

波波老师5年集大成之作，算法与数据结构系统学习，考试、面试、竞赛通用

2603 学习 · 1086 问题

查看课程

相似问题

这里解析均摊复杂度的计算过程不太对！

回答 1

一个关于职业发展方向上的问题

回答 1

一个关于专业的问题

回答 1

关于一题多解的情况如何应对呢

回答 1

python deque出列计算速度

回答 1

打开慕课网App查看更多内容