временная сложность и геометрические ряды, вложенные циклы

Question

У меня есть следующий код, и я пытаюсь понять, какова его временная сложность:

for (int i = 1 ; i <= n ; i = i*2)
    for (int j = 1 ; j <= n ; j = j*2)
        for (int k = 1 ; k <= j ; k++)

То, что я сделал, было:
первый цикл запускает журнал n раз, второй цикл также запускает журнал n раз, а третий цикл представляет собой геометрический ряд

так в целом у меня время работы будет: n*(log(n))^2

Это правильно?
спасибо!

Answer 1

Теоретически вы правы, сложность составляет n*(log(n))^2.

Для практических целей итерация для n = 1000:

i = 1; n= 1000; j= 1;k =1; result = 0
while i<=n:
    j=1
    while j<=n:
        k=1
        while k<=j:
            result = result+1
            k = k+1
        j = j*2
    i = i*2
print(result)

и мы получаем результат = 10230

поэтому фактическое значение результата мы получаем по формуле floor(logn)+1) * (2 ^ floor(logn)+1) - 1). Для n = 1000 это 10 * (2 ^ 10-1)

для n = 2 ^ 25 мы получаем результат 1744830438, который также удовлетворяет формуле = 26 * ((2 ^ 26) -1) = 1744830438.