Временная сложность для следующего цикла кода?

Question

Мне просто нужно, чтобы кто-то объяснил мне одну строку кода, я не очень понимаю. * это просто псевдокод

m: = 1, l := 0, s:= 0:
while m <= n do 
    for j = n-m to n do :
      l:= l + 1
    od 
     for j = 1 to [log n] do 
       s: = s +1 
     od 
     m := 3m 
 od 

Я понимаю, что второй цикл for - это log n time, а цикл while - это log base 3 n time, но я не совсем понимаю первый цикл for? Может кто-нибудь объяснить, это просто о (п)? Что на самом деле делает j = nm?

Answer 1

Первый цикл for работает от n-m до n. Так что он имеет m итераций. В последней итерации цикла while m в основном n, поэтому он работает линейно в n. Но общая сложность лучше, чем O(n log n)

В общей сложности у вас есть столько итераций

(1 + log n) + (3 + log n) + (9 + log n) + ... + (n + log n)  ( log_3 n terms )
 = log_3 n * log n + (1 + 3 + 9 + ... + n)   ( n can be written as 3^(log_3 n) )
 = log_3 n * log n + (3^0 + 3^1 + 3^2 + ... + 3^(log_3 n))   (see this as a base 3 number. 11 is smaller than 100)
<= log_3 n * log n + 3^(1 + log_3 n)
 = log_3 n * log n + 3 * n

Таким образом, доминирующий член равен n и, следовательно, общая сложность равна O(n).