计算嵌套for循环的复杂性

本文介绍了计算嵌套for循环的复杂性的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 我想计算这个嵌套for循环的复杂性： $ b $ pre $ s = 0; （j = 1; j <= i; j * = 2） s ++;对于（i = 1;i≤n; i * = 2），

我用什么策略来找到这段代码的大O复杂性？

解决方案

外层循环遍历1,2,4,8，... n lg n ）步骤，因为您只能加倍一次O（lg n ）次，直到按 n 。

内层循环也是一样的。它只能到达 i ，但是在外循环的最后迭代中， i 达到了最大值，这又是 n ，所以也就是O（lg n ）。

把它们放在一起给出一个O（（lg n ）） ²），通常缩写为O（lg² n ）。

I want to calculate the complexity of this nested for loop:

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

What strategy do I use to find the Big O complexity of this piece of code?

解决方案

The outer loop marches through 1, 2, 4, 8, ... n, which takes O(lg n) steps because you can only double one O(lg n) times until you hit n.

The inner loop does the same. It only goes up to i, but in the final iteration of the outer loop, i reaches its maximum value which is again n, so that's also O(lg n).

Putting this together gives an upper bound of O((lg n)²), which is commonly abbreviated O(lg² n).