Расчет большой сложности этих алгоритмов O?

Question

Я пытаюсь понять нотацию Big O следующих двух алгоритмов ниже, но у меня проблемы.

Первый:

public static int fragment3 (int n){ 
int sum = 0; 
for (int i = 1; i <= n*n; i *= 4) 
    for (int j = 0; j < i*i; j++) 
    sum++; 
    return sum; 
} //end fragment 3 

Ответ должен быть O(n^4). Когда я пытаюсь сделать это сам, это то, что я получаю: Я смотрю первый цикл цикла и думаю, что он запускает n^2 logn раз. Затем для внутреннего цикла for он запускает n раз + время выполнения внешнего цикла, которое равно n^3 logn раз. Я знаю, что это неправильно, но просто не понимаю.

Для фрагмента кода ниже ответ O(n^9).

public static int fragment6(int n) { 
int sum = 0; 
for(int i=0; i < n*n*n; i++) { 
    if(i%100 == 0) { 
    for(int j=0; j < i*i; j += 10) 
     sum++; 
    } // if 
    else { 
    for(int k=0; k <= i; k++) 
     sum++; 
    } // else 
} // outer loop 

return sum; 
} // fragment 6 

Когда я пытаюсь это я получаю: n^3 для внешнего для цикла. для оператора if я получаю n, для второго цикла цикла я получаю n + другой для цикла и если оператор, делая его n^5. Наконец, я получаю n для финального цикла, и все добавляет до O(n^6).

Что я делаю неправильно и каков правильный способ получить его O(n^9) сложности?

Answer 1

Первый случай:

• Последний пробег внутренней петли с I = п^2, работает при п^4. Внешняя петля до n^2, но с использованием экспоненциального роста. Для суммирования сумма по всем циклам внутреннего цикла, но последняя меньше последнего прогона. Таким образом, внутренний цикл, по существу, вносит вклад O (1).

Второй случай:

• 100% п == 0 не имеет значения, на самом деле в O мышления
• еще часть не имеет значения, это намного меньше, чем основной части
• внешнего контура работаю от 0 до п^3 => п^3
• внутреннего контур проходит от 0 до п^6 => N^6
• раз наружного контура внутреннего контура => п^9

Answer 2

Ваш подход к вычислению big-O ошибочен, и вы сделали ошибки вычислений.

В некоторых общих случаях вы можете взять худший случай число итераций и умножить их вместе, но это не метод звука и не в тех случаях, как это:

for (i = 1; i < n; i *= 2) { 
    for (j = 0; j < i; j++) { 
     sum++; 
    } 
} 

Здесь наружные пробеги петли log_2 (n) раз, а наихудший случай внутреннего цикла - n итераций. Таким образом, неправильный метод, который вы используете, скажет вам, что сложность этого кода - O (n log n).

Правильный метод состоит в том, чтобы точно подсчитать количество итераций и приблизиться только в конце. Число итераций на самом деле:

1 + 2 + 4 + 8 + ... + 2^k 

где 2^k - наибольшая мощность двух меньше n. Эта сумма равна 2^(k + 1) - 1, что меньше 2n.Таким образом, точная сложность O (n).

Применяя эту идею к вашему первому примеру:

for (int i = 1; i <= n*n; i *= 4) 
    for (int j = 0; j < i*i; j++) 
     sum++ 

i принимает значения 4^0, 4^1, 4^2, ..., 4^k где 4^k самая большая мощность 4 меньше или равно n^2.

Внутренний цикл выполняет i^2 раз для заданного значения i.

Так в целом, внутренняя sum++ выполняется много раз:

(4^0)^2 + (4^1)^2 + ... + (4^k)^2 
= 2^0 + 4^2 + ... + 4^2k 
= 16^0 + 16^1 + ... + 16^k 
= (16^k - 1)/15 

Теперь по определению k мы имеем n^2/4 < 4^k <= n^2. Итак, n^4/16 < 4^2k <= n^4, и с 16^k = 4^2k мы получаем, что общее количество раз, когда выполняется внутренний цикл, равно O (16^k) = O (n^4).

Второй пример можно решить, используя аналогичный подход.

Answer 3

Для первого.

Давайте посмотрим на внутренний цикл ..

На первой итерации внешнего цикла (I = 1) он работает 1 раз. На второй итерации (i = 4) выполняется 16 (4 * 4) раз. На третьей итерации (i = 16) выполняется 256 (16 * 16) раз. В общем случае на (k + 1) -ой итерации внутренней петли внешнего контура выполняется раз, как на этой итерации. Таким образом, общее число итераций будет

Теперь, сколько чисел в этой сумме мы будем иметь? Чтобы определить, что мы должны взглянуть на внешний цикл. В нем я вырастаю как , пока не достигнет . Таким образом, общее число итераций составляет .

Это означает, что общее число трасс внутренней петли

(понижая все числа от суммы, но последний).

Теперь мы знаем, что внутренний цикл работает как минимум раз, поэтому мы не быстрее O (n^4).

Теперь

Решение для N,

где C является константой, поэтому мы не медленнее, чем O (N^4).