Нахождение временной сложности этих двух алгоритмов? - PullRequest
Новая
       43

Нахождение временной сложности этих двух алгоритмов?

0 голосов
/ 19 февраля 2020

Вот первый алгоритм, 

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

Вот второй алгоритм 

sum = 0;
for( i=1; i<n; i++ )
    ( j=1; j<i*n; j++ )
        if( j%1 == 0 )
            for( k=0; k<j; k++ )
                sum++;

Может кто-нибудь помочь мне найти Big O для этих двух алгоритмов? Я попытался сделать это, и я получил n ^ 5, но когда я проверил это, сравнивая время выполнения алгоритма n ^ 5 и этих алгоритмов, была огромная разница ... Хотя оба эти алгоритма имели более или менее равную работу времена, что означает, что их временная сложность одинакова.

Если кто-то может тогда, пожалуйста, предоставьте возможный способ проанализировать эти два алгоритма и найти временные сложности обоих. Спасибо

Примечание: я также пытался сравнить его с алгоритмами n ^ 4 времени, и все еще была огромная разница между временем выполнения ... Я могу также указать значения времени выполнения всех этих разные алгоритмы, если требуется.

1 Ответ

2 голосов
/ 19 февраля 2020

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

sum_{i=1}^{n-1} sum_{j=1}^{i*n} j =
sum_{i=1}^{n-1} i * n * (i*n + 1) / 2 = 
0.5 * sum_{i=1}^{n-1} i^2 * n^2 + i*n = 
0.5 * (n^2 * sum_{i=1}^{n-1} i^2 + n * sum_{i=1}^{n-1} i) = 
0.5 * (n^2 * \Theta(n^3) + n * \Theta(n^2)) = \Theta(n^5)

Итак, вы правы. Но будьте осторожны, это асимптотическая c сложность времени, которая может отличаться от измеренного времени работы процессора.

И то же самое для второго алгоритма (с небольшой разницей), как всегда, j%1 равно нулю для всех j > 0.

...