人们在处理这些任务时常犯的一个错误是将事情看作“直截了当”,但在许多场景中(比如这个)情况并非如此。
正确的方法是尝试“跟随”程序执行的计算步骤,以及每个步骤需要多长时间来确定时间复杂性(也包括内存复杂性)。
我建议写下前5个左右迭代的发生情况,并尝试找出其中的模式。
因此,在这种情况下,第一个循环将从N开始,一直到0,而索引每次减半。你说的对,它意味着O(log(N)),但让我们写下一些最初的迭代的索引:
i=N
i=N/2
i=N/4
i=N/8
i=N/16
...
现在,真正的事情发生在第二个for
循环中,它在第一个循环内部。
首先,你可以看到第二个索引j
与i
有依赖关系,这应该立即引起我们的警惕,我们应该特别注意它。
第二个循环从0到当前迭代的i
进行,增量为1。起初,你可能会说它是O(n)
,因为变化是增加1,并且它从0到特定已知整数。但由于该整数是动态变化的,你不能真正地说出来,必须知道i
将会是什么。
所以让我们写出上面每个迭代的内部循环的第一次迭代:
i=N -> | j=0 | j=1 | j=2 | ... | j=N |
i=N/2 -> | j=0 | j=1 | j=2 | ... | j=N/2 |
i=N/4 -> | j=0 | j=1 | j=2 | ... | j=N/4 |
i=N/8 -> | j=0 | j=1 | j=2 | ... | j=N/8 |
i=N/16 -> | j=0 | j=1 | j=2 | ... | j=N/16 |
...
现在,我上面写的每个“盒子”(
| |
)都是程序执行的步骤。正如我之前所说,我们还需要知道每个步骤需要多长时间。在这种情况下,每个步骤(每次迭代)包括一次变量(
count
)增量操作,我们将其视为
O(1)
(常数)。
我们应该做的最后一件事是总结我们上面提到的所有步骤及其成本:
第一行将运行N次(0,1,2,..,N)- 每次步骤的成本为
O(1)
。-> 所以它将是
N*1 = N
第二行将运行N/2次(0,1,2,..,N/2)- 每次步骤的成本为
O(1)
。-> 所以它将是
(N/2)*1 = N/2
第三行将运行N/4次(0,1,2,..,N/4)- 每次步骤的成本为
O(1)
。-> 所以它将是
(N/4)*1 = N/4
等等。
当我们总结起来时,程序的成本将是:
N+(N/2)+(N/4)+(N/8)+...+~(N/N) = N * ( 1 + (1/2) + (1/4) + (1/8) +... )
( 1 + (1/2) + (1/4) + (1/8) +... )
是一个简单的已知数学级数。(您可以从一些网站或通过谷歌搜索来了解这些或更复杂的级数的结果)。 最多等于
2-(2/N)
。
因此,最终成本将是:
N * ( 2 - (2/N) ) = 2N - 2
,总体上为
O(N)
。
对于这个问题,这个答案相当长而且详细,但我试图展示一种“思考方式”,而不仅仅是解决问题。我希望它能帮助您(和其他人)在类似这样的问题上思考不同,尝试仔细检查每个循环和每个步骤,以及最重要的(并且经常被忽视)每个步骤的成本。
N
的count
将会给你一些线索。(好吧,那就看这里:https://ideone.com/8GH8Me) - Andy Turnerfor (int i = 1; i < n; i *= 2)
,由于步长的原因实际上具有对数复杂度。或者像for(foo(); bar(); baz())
,这完全取决于方法。再比如for (int i = 0; i < n; i++) { for (int j = i; j < i + 5; j++) {...}}
,这不是二次的而是线性的。不要只是按照模式学习,你必须真正理解大O符号的工作原理并正确分析它。 - Zabuzard