Временная сложность программы с множественным алгоритмом - PullRequest
Новая
       18

Временная сложность программы с множественным алгоритмом

1 голос
/ 12 июля 2020

Итак, насколько я знаю, если моя программа имеет что-то вроде этого - 

     method 1:
     for (int i = 0; i < N; i++) 
       statement;

Временная сложность алгоритма будет O(N), или 

     method 2:
     for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
       statement;

Это будет O(N^2)

Что, если моя программа представляет собой комбинацию нескольких таких циклов по отдельности? Например - 

method1: statement;
method2: statement;

или 

method1: statement;
method1: statement;
method1: statement;

Увеличит ли это общую временную сложность системы? Или просто возьмите самое высокое из них и go с этим?

1 Ответ

3 голосов
/ 12 июля 2020

Когда циклы вложены, временная сложность увеличивается. Например, - 

loop(1 to n1):
    loop(1 to n2):
        loop(1 to n3):
            # Some code here

. В приведенном выше случае временная сложность будет O( n1*n2*n3 ). Когда циклы выполняются параллельно, увеличивается временная сложность. Например, - 

loop(1 to n1):
    # Some code here
loop(1 to n2):
    # Some code here
loop(1 to n3):
    # Some code here

В приведенном выше случае временная сложность будет O( n1 + n2 + n3 ).

Что, если моя программа представляет собой комбинацию нескольких таких циклов по отдельности?

1. Первый пример - 

method1: statement;
method2: statement;

В приведенном выше коде ваш метод1 имеет временную сложность O (N), а метод2 имеет временную сложность O (N ^ 2). Итак, у нас есть общая временная сложность - 

O( N ) + O( N^2 ) = O( N + N^2 ) = O( N^2 )

В верхней границе временной сложности мы обычно игнорируем младшие члены и упрощаем окончательную временную сложность, которая мы получили. Таким образом, в приведенном выше примере ответ будет O(N^2).

2. Второй пример - 

method1: statement;
method1: statement;
method1: statement;

Мы можем вычислить временную сложность аналогичным образом. У нас будет временная сложность - 

O( N ) + O( N ) + O( N ) = O ( 3*N ) = O ( N )

Еще одно правило при вычислении верхней границы временной сложности состоит в том, что мы игнорируем постоянные члены , которые мы получаем в нашей временной сложности.

Эти правила можно легко распространить на аналогичные примеры. Независимо от того, сколько циклов параллельно, мы возьмем суммирование каждого l oop и применим два вышеуказанных правила, и это будет наша окончательная временная сложность. Точно так же для вложенных циклов мы умножим временную сложность каждого l oop, и это будет нашим окончательным результатом.

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

...