O(n)运行时算法

Question

O(n)根据我们的教授,下面的算法有运行时间,但是我很困惑为什么它不是 O(n log(n)),因为外部循环可以运行log(n)多次,内部循环可以运行多达n几次.

Algoritme Loop5(n) 
i = 1 
while i ? n 
    j = 1 
    while j ? i 
       j = j + 1 
    i = i?2

Answer 1

你的教授是对的,运行时间是O(n).

在i外部while循环的第 - 次迭代中,当我们有i=2^kfor时k=0,1,...,log n,内部while循环进行O(i)迭代.(当我说log n我的意思是基数为2的对数时log_2 n.)

运行时间O(1+2+2^2+2^3+...+2^k)为k=floor(log n).这总计为O(2^{k+1})是O(2^{log n}).(这是从几何级数的部分和的公式得出的.)

因为2^{log n} = n,总的运行时间是O(n).

对于感兴趣的人来说,这是一个证据,证明两个人的权力真正归结为我所声称的总和.(这是一个非常特殊的一般结果.)

要求.对于任何自然k,我们有1+2+2^2+...+2^k = 2^{k+1}-1.

证明.需要注意的是(2-1)*(1+2+2^2+...+2^k) = (2 - 1) + (2^2 - 2) + ... + (2^{k+1} - 2^k),所有2^i的0<i<k+1抵消,除了i=0和i=k+1,和我们留下的2^{k+1}-1.QED.