Столкнувшись с проблемой анализа этого сегмента кода, чтобы найти BigO

Question

for (int i = 1; i <= Math.pow(2, n); i = i * 2) {
    for (int j = 0; j <= Math.log(i); j++) {
        sum = i + j;
        System.out.println(sum); // we would like to print the sum..
    }
}

Как подсчитать количество примитивных операций, выполняемых моим кодом?

Answer 1

Анализируя первый цикл, вы можете увидеть, что предел равен 2 ^ n , но вы можете видеть, что шаг приращения равен i = ix 2 , поэтому сколько умножений до васдостичь предела?Ответ очевиден: n .

Внутренний цикл, в худшем случае, сколько итераций будет выполнено?Поскольку это зависит от максимального значения, которое когда-либо будет принимать первая переменная цикла ( i ), то это натуральный логарифм этого значения, другими словами, log (2 ^ n) .

Подводя итог, можно сказать, что общая сложность алгоритма составляет O(n * log(2^n)), что упрощает до O(n*n), убирая показатель степени (как оперативно предложил @Andreas).