问嵌套循环的大O (int = 0；j< i；j++)
EN

Stack Overflow用户

提问于 2020-01-02 23:49:18

回答 1查看 1.5K关注 0票数 3

for (int i = n; i > 0; i /= 2) {
   for (int j = 0; j < i; j++) {
     //statement
   }
}
Answer: O(N)

我知道for (int i = n; i > 0; i /= 2)的第一个循环会导致O(log N)。

第二个循环for (int j = 0; j < i; j++)依赖于i，并将首先迭代i次，然后是i / 2、i / 4、.时间。( i依赖于n)

我不知道第二个循环的大O，但我认为答案是O(log N * something)，其中O(log N)是外部循环，something是内环？

你是怎么得到O(N)的

big-o

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-01-03 00:26:34

由于O(log n)的存在，外部循环的复杂性为i /= 2。但内环则要复杂一些。

内循环的复杂性为O(i)，但外部循环的每一次迭代都会改变i。与外部循环相结合，您将得到O(n / log n)的复杂性。如下所示：

内循环正在执行的步骤数与1/(2n)之和类似，如https://en.wikipedia.org/wiki/1/2_%2B_1/4_%2B_1/8_%2B_1/16_%2B_⋯上所描述的。首先您正在执行n步骤，然后只执行n/2步骤，然后执行n/4步骤等等，直到您只执行2步骤，最后执行1步骤。这综合了2n的结果。总之，您运行内环log n时间(由外部循环定义)。这意味着内循环以平均2n / log n时间运行。所以你有一个复杂的O(n / log n)。

使用O(log n)的外循环和O(n / log n)的内环，您可以得到O(log n * n / log n)，可以简化为O(n)。

票数 3

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/59571492

复制

相似问题

问嵌套循环的大O (int = 0；j< i；j++)
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问嵌套循环的大O (int = 0；j< i；j++)EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问嵌套循环的大O (int = 0；j< i；j++)
EN