Каким образом следующий алгоритм имеет временную сложность 0 (n ^ 2) - PullRequest
Новая
       21

Каким образом следующий алгоритм имеет временную сложность 0 (n ^ 2)

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

Итак, я новичок в изучении временной сложности, и если кто-то может объяснить, как: 

For (i := 0; i < n; i = i + 1)
    For (j := i; j < n; j = j + 1)

имеет временную сложность O (n 2 ), Я так понимаю, это n работа проделана n раз, но как? Также, если бы вы могли сказать мне, что означает :=, это было бы здорово.

1 Ответ

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

Давайте немного изменим код: 

x = 0
For (i := 0; i < n; i = i + 1)      //it says: let i be 1, 2, ..., until n - 1
    For (j := i; j < n; j = j + 1)  //it says: let j be i, i+1, ..., until n - 1
        x = x + 1

Каким будет значение x?

Легко посчитать, сколько раз будет выполняться второй For .

Он начинается с 0 до n-1, затем от 1 до n-1, от 2 до n-1, ..., от n-1 до n-1. Это означает, что в операциях: 

0  1  2 ... (n-1) = (n-1) - 0 + 1 operations =    n    operations
1  2  ..... (n-1) = (n-1) - 1 + 1 operations = (n - 1) operations
2  ........ (n-1) = (n-1) - 2 + 1 operations = (n - 2) operations
        .
        .
        .
      (n-1)                                  =    1    operation 
                                               ___________________
                                              (1 + 2 + 3 + ... + n) 
                                               = (n + 1) * (n / 2) 
                                               =     (n² + n)/2  operations

Мы видим, что эти For суммируют (n² + n)/2 операции, поэтому x = (n² + n)/2.

При анализе сложности мы следуем некоторым правилам. Я опишу те, которые полезны в этом случае:

1 Удалить мультипликативные константы : 

O((n² + n)/2) = O(0.5 * (n² + n)) = O(n² + n)

Теоретически, когда n переходит в бесконечность, эти константы не повлияют на поведение функции.

2 Удалить члены с более низким классом мощности : 

O(n² + n) = O(n²)

Теория, лежащая в основе этого, заключается в том, что переменная с самым большим классом мощности (n² в данном случае) управляет поведением функции по сравнению с переменными с самым низким классом.

Вот почему мы можем утверждать, что сложность этих вложенных циклов составляет O (n²).

...