Как рассчитать сложность алгоритма?

Question

Мне нужно рассчитать сложность этого алгоритма, я попытался его решить и нашел ответ O (nlogn). Правильно ли это? Если нет, объясните пожалуйста.

for (i=5; i<n/2; i+=5) 
{ 
    for (j=1; j<n; j*=4) 
      op; 

    x = 3*n; 
    while(x > 6) 
      {op; x--;} 
} 

Answer 1

Katrina, В этом примере мы получили O (N * Log (N)) `

for (int i= 0; i < N; i++) { 
     c= i; 
     while (c > 0) { 
     c= c/2 
     } 
    } 

Как всегда у вас есть другая для этого включает в себя это как bucles. Im не совсем уверены, чтобы понять, как она работает алгоритм, но в стандартный способ, учитывая другое для bucle, должно быть O (п п журнал п

for (int j= 0; i < N); j++) { --> O(n) 
    for (int i= 0; i < N; i++) { O(n) 
     c= i; 
     while (c > 0) { O(logn) 
     c= c/2  O(1) 
     } 
    } 
    } ? 

Aftermath в этом стандартном алгоритме будет O (п) * O (N) * O (LOGN) * O (1)

Так что, я думаю, что вы забыли включить другую O (п) ) Надеюсь, что это помогает

Answer 2

посчитаем число итераций в каждый цикл.

Наружный контур for (i=5; i<n/2; i+=5) шаги через все значения между 5 и n/2 с шагом 5. Таким образом, потребуется приблизительноn/10 - 1 итераций.

Есть две внутренние петли. Рассмотрим первый: for (j=1; j<n; j*=4). Это выполняет все значения формы 4^x между 1 и n для целых чисел x. Самое низкое значение x для этого - 0, а наибольшее значение - x, которое соответствует 4^x < n - то есть целому числу, ближайшему к log_4(n). Таким образом, обозначая итерации на x, мы имеем итерации 0, 1, ..., log_4(n). Другими словами, для этого цикла мы имеем приблизительно log_4(n) + 1 итераций.

Теперь рассмотрим второй внутренний цикл. Он выполняет все значения от 3 * n до 7. Таким образом, число итераций составляет приблизительно 3 n - 6.

Все остальные операции имеют постоянное время работы и поэтому могут игнорироваться.

Как мы собираем это вместе? Две внутренние циклы выполняются последовательно (то есть, они не вложены друг в друга), так что время выполнения для них обоих вместе, является просто суммой:

(log_4(n) + 1) + (3 n - 6) = 3 n + log_4(n) - 5. 

Внешний контур и две внутренние циклы, однако, вложенными. Для каждой итерации внешнего цикла выполняются как внутренние, так и внутренние. Поэтому мы умножаем число итераций внешнего с общим внутренним:

(n/10 - 1) * (3 n + log_4(n) - 5) = 
     = 3 n^2/10 + n log_4(n)/10 - 7 n/2 - log_4(n) + 5. 

Наконец, сложность часто выражаются в Big-O нотации - то есть, мы заинтересованы только в том порядке, из время выполнения. Это означает две вещи. Во-первых, мы можем игнорировать все постоянные факторы во всех терминах. Например, O(3 n^2/10) становится только O(n^2).Таким образом, мы имеем:

O(3 n^2/10 + n log_4(n)/10 - 7 n/2 - log_4(n) + 5) = 
     = O(n^2 + n log_4(n) - n - log_4(n) + 1). 

Во-вторых, мы можем игнорировать все термины, которые имеют более низкий порядок, чем срок с самого высокого порядка. Например, n имеет более высокий порядок, чем 1, поэтому у нас есть O(n + 1) = O(n). Таким образом, мы имеем:

O(n^2 + n log_4(n) - n - log_4(n) + 1) = O(n^2). 

И наконец, у нас есть ответ. Сложность алгоритма, описываемого вашим кодом, - O(n^2).

(На практике, один никогда бы не вычислить (приблизительное) число итераций, как мы делали здесь. Облегчение мы сделали в предыдущем шаге может быть сделано раньше, что делает расчеты гораздо проще.)

Answer 3

Как Фредрик упомянутая временная сложность первой и третьей петель O(n). время для второго цикла - O(log(n)).

Так сложность следующего алгоритма O(n^2).

for (i=5; i<n/2; i+=5) 
{ 
for (j=1; j<n; j*=4) 
     op; 

x = 3*n; 
while(x > 6) 
     {op; x--;} 
} 

Следует отметить, что сложность следующий алгоритм O(n^2*log(n)), который не то же самое с выше алгоритма.

for (i=5; i<n/2; i+=5) 
{ 
for (j=1; j<n; j*=4) 
    { 
    op; 
    x = 3*n; 
    while(x > 6) 
     {op; x--;} 
    } 
}