Порядок роста, сложный для петель

Question

Для следующего фрагмента кода, каков порядок роста с точки зрения N?

int sum = 0; 
for (int i = 1; i <= N; i = i*2) 
    for (int j = 1; j <= N; j = j*2) 
    for (int k = 1; k <= i; k++) 
     sum++; 

я понял, что есть ЛГН термин, но я застрял на оценку этой части: ЛГНА (1 + 4 + 8 + 16 + ....). Каким будет последний член последовательности? Мне нужен последний термин для вычисления суммы.

Answer 1

Вы геометрическая прогрессия в ваших внешних петлях, так что замкнутая форма на сумму которого вы хотите взять журнал:

1 + 2 + 4 + ... + 2^N = 2^(N+1) - 1 

Чтобы быть точным, ваша сумма

1 + ... + 2^(floor(ld(N)) 

с ld обозначая логарифм по основанию 2.

наружные две петли являются независимыми друг от друга, в то время как внутренний цикл зависит только от i. Существует одна операция (приращение) в самом внутреннем цикле, что означает, что количество посещений самой внутренней петли равно суммарному результату.

\sum_i=1..(floor(ld(N))) { 
     \sum_j=1..(floor(ld(N))) { 
      \sum_k=1..2^i { 1 } 
     } 
    } 

    // adjust innermost summation bounds 
= \sum_i=1..(floor(ld(N))) { 
     \sum_j=1..(floor(ld(N))) { 
      -1 + \sum_k=0..2^i { 1 } 
     } 
    } 

    // swap outer summations and resolve innermost summation 
= \sum_j=1..(floor(ld(N))) { 
     \sum_i=1..(floor(ld(N))) { 
      2^i 
     } 
    } 

    // resolve inner summation 
= \sum_j=1..(floor(ld(N))) { 
     2^(floor(ld(N)) + 1) - 2 
    } 

    // resolve outer summation 
= ld(N) * N - 2 * floor(ld(N)) 

Это составляет O(N log N) (второе слагаемое в выражении равно нулю асимптотически WRT к первой) в Big-Oh обозначении.

Answer 2

В моем понимании, внешний цикл будет принимать log N шагов, следующий цикл будет также принимать log N шагов, а внутренний цикл будет принимать самое N шагов (хотя это очень грубая оценка). В целом, цикл имеет сложность выполнения не более ((log N)^2)*N, что, вероятно, может быть улучшено.