какой из них больше O (N ^ 2 * log (N ^ 2)) или O (N ^ 3)?

Question

Я хочу найти сложность времени для следующего:

int i, j, k; 
for(i = 1; i <= N^2+N^2; i = i + 3)  ***//O(N^2)*** 
{
     for(j = i; j <= N ; j = j + 3)  ***//O(N^3)***

     { 
     } 

     for(k = 1; k<= N^2 ; k = k * 2)  ***//O(log(N^2)*N^2)***

     { 
     } 
} 

Я решил это следующим образом, но меня смущает, больше ли O (N ^ 2 * log (N ^ 2)) или O (N ^ 3)

Answer 1

Это очень хитрый кусок кода, время выполнения которого более нюансировано, чем я ожидал. Вот что у вас есть:

int i, j, k; 
for(i = 1; i <= N^2+N^2; i = i + 3)
{
     for(j = i; j <= N ; j = j + 3)
     { 
     } 

     for(k = 1; k<= N^2 ; k = k * 2)
     { 
     } 
} 

@ Пол Ханкин сделал важное замечание, что, когда i становится достаточно большим, первый l oop никогда не выполняется. В результате, чтобы проанализировать этот l oop, нам нужно рассмотреть два случая: один, где верхний l oop выполняет некоторое количество итераций, и один, где этого нет.

To сделайте это, обратите внимание, что ваш код по существу эквивалентен следующему, где я разбил внешний l oop на два меньших цикла:

int i, j, k; 
for(i = 1; i <= N; i = i + 3)
{
     for(j = i; j <= N ; j = j + 3)
     { 
     } 

     for(k = 1; k<= N^2 ; k = k * 2)
     { 
     } 
} 

for(i = N+1; i <= N^2+N^2; i = i + 3)
{
     for(k = 1; k<= N^2 ; k = k * 2)
     { 
     } 
} 

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

Если сомневаетесь, поработайте наизнанку!

и начните заменять более глубокие циклы операторами, указывающими, сколько работы они выполняют. Давайте начнем с l oop, который насчитывает от 1 до N ² путем многократного удвоения. То, что l oop будет работать примерно log N ² = 2 log N = Θ (log n) раз, поэтому мы получаем это:

int i, j, k; 
for(i = 1; i <= N; i = i + 3)
{
     for(j = i; j <= N ; j = j + 3)
     { 
     } 

     do Θ(log N) work;
} 

for(i = N+1; i <= N^2+N^2; i = i + 3)
{
     do Θ(log N) work;
} 

Аналогично, l oop который рассчитывает от i до N, работает Θ (N - i), поэтому мы получаем это:

int i, j, k; 
for(i = 1; i <= N; i = i + 3)
{
     do Θ(N - i) work;
     do Θ(log N) work;
} 

for(i = N+1; i <= N^2+N^2; i = i + 3)
{
     do Θ(log N) work;
} 

Теперь сосредоточимся на втором из этих двух циклов. Эта вторая l oop выполняется Θ (N ² ) раз (поскольку (2N ² - N) / 3 = Θ (N ² )), выполняя O (log N) работает каждый раз, поэтому он выполняет Θ (N ² log N) общей работы:

int i, j, k; 
for(i = 1; i <= N; i = i + 3)
{
     do Θ(N - i) work;
     do Θ(log N) work;
} 

do Θ(N^2 log N) work;

Теперь у нас есть первый l oop. Нам нужно подвести итог (N - i + log N) по i = 1, 4, 7, 10, 13 и т. Д. c. Сумма N - i из i = 1, 4, 7, 10, ..., N получается равной Θ (N ² ), и один из способов увидеть это - использовать эту картинку, чтобы увидеть что это в конечном итоге примерно равно площади (то есть что-то, что растет квадратично) треугольника:

 *
 ****
 *******
 **********
 *************

Сумма log N, запущенная Θ (N) раз, составляет Θ (N log N) общей работы, таким образом, мы получаем l oop, требующее Θ (N ² ) времени, поскольку N ² доминирует над N log N. Следовательно, мы имеем

do Θ(N^2) work;
do Θ(N^2 log N) work;

Таким образом, общее время выполнения составляет Θ (N ² log N) .

Возвращаясь к вопросу, который вы задали, как: does (N ³ ) сравнить с Θ (N ² log N)? Если мы отменим N ² слагаемых, которые они разделяют, у нас останется вопрос о том, как N сравнивается с log N. Мы знаем, что log N растет намного, намного медленнее, чем N, и поэтому N ² log N = o (N ³ ).

Надеюсь, это поможет!

Answer 2

Попробуйте ограничить эти два выражения:

L = lim_{N \to \infty} N^3/(N^2 log(N^2)) = lim_{N \to \infty} N/log(N^2)

Как вы можете найти подсказку в комментариях, log(N^2) = 2 log(N). Теперь мы имеем:

L = 1/2 lim_{N \to \infty} N/log(N)

Поскольку рост N превышает log(N), мы можем заключить, что L = \infty. Следовательно, данный алгоритм имеет вид O(N^3).