O (n) Czas trwania algorytmu

Question

poniżej Algorytm jest czas pracy O(n) według naszego profesora jednak jestem mylić, dlatego nie jest O(n log(n)), ponieważ zewnętrzna pętla może obsługiwać do log(n) razy i Wewnętrzna pętla może obsługiwać do n razy.

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

Answer 1

Twój profesor miał rację, czas odtwarzania jest O(n).

W i -tym iteracji pętli while zewnętrznej, gdy mamy do k=0,1,...,log ni=2^k, podczas gdy wewnętrzna pętla umożliwia O(i) iteracji. (Kiedy mówię log n mam na myśli podstawa logarytmu log_2 n-2).

Czas pracy jest O(1+2+2^2+2^3+...+2^k) dla k=floor(log n). To sumuje się na O(2^{k+1}), która jest O(2^{log n}). (To wynika z formula for the partial sum of geometric series.)

Ponieważ 2^{log n} = n, całkowity czas działania to O(n).

Dla zainteresowanych, oto dowód, że moce dwojga naprawdę sumują się do tego, o czym twierdzę, że się sumują. (Jest to bardzo szczególny przypadek bardziej ogólnego wyniku).

Roszczenie. Dla każdego naturalnego k, mamy 1+2+2^2+...+2^k = 2^{k+1}-1.

Dowód. Zauważ, że (2-1)*(1+2+2^2+...+2^k) = (2 - 1) + (2^2 - 2) + ... + (2^{k+1} - 2^k), gdzie wszystkie 2^i dla 0<i<k+1 znikają, z wyjątkiem i=0 i i=k+1, a pozostajemy z 2^{k+1}-1. CO BYŁO DO OKAZANIA.