Как найти время выполнения следующего алгоритма?

Question

Я бегу Большой O , но полностью потерян.

while l oop только запуск N/2 и for l oop также N/2, поэтому он становится N**2?

Правильно ли я думаю ?

# Block (a)
sum = 0;
n = N
while n > 0: 
    for i in range(0, n):
        sum += 1;
    n = n // 2

# running times: N/2 * N/2 = N^2/4 >> N^2?

# Block (b)
sum = 0
i = 1
while i < N:
    for j in range(0, i):
        sum += 1
    i = i * 2

# running times: N^2??

# Block (c)
sum = 0
i = 1
while i < N:
    for j in range(0, N):
        sum += 1
    i = i * 2

# running times: N^2??

Answer 1

Посмотрите на

  n = n // 2

или

  i = i * 2

Деление (n = n // 2) уменьшает n намного быстрее , а затем вычитание (n = n - 1). Ваше решение O(N**2) было бы правильным для n = n - 1; для деления (n = n // 2) имеем

  n = N
  while n > 0: 
    for i in range(0, n):
        sum += 1;

    n = n // 2

Давайте развернем внешнее l oop (while n > 0:)

 0..N              - N      items to sum
 0..N / 2          - N/2    items to sum
 0..N / 4          - N/4    items to sum
 ...
 0..N / 2**p       - N/2**p items to sum
 ...
 0..N / 2**(log N) - 1      item  to sum

Итак, имеем ( верхняя граница ):

 N * (1 + 1/2 + 1/4 + ... 1/2**p + ...) = 2 * N = O(N)

текучая известь линейная .