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

Question

Алгоритм сортировки списка L1 длиной n:

1) Создать новый список L2

2) Переместить самый большой элемент L1 в начало L2

3 ) Выполните 2) до тех пор, пока L1 не станет пустым

4) Распечатайте L2

Может кто-нибудь выяснить, в чем состоит сложность O ()? Сначала я думал, что это O (n * log (n)), но я больше не уверен, теперь я думаю, что это O (n ^ 2).

Answer 1

Допустим, у вас есть список из 10 элементов.

На шаге 2 вам сначала нужно отсканировать весь список, чтобы найти самый большой элемент и перейти к нему в списке № 2.

Таким образом, сканирование всего списка составляет (10 + 9 + 8 + ... + 1) операций = 55.

Для 100 элементов это будет (100 + 99 + ... + 1), что составляет 5050

Теперь для n элементов у вас будет (n + (n-1) + ... + 1) операций, которые (n+1)*n/2 = O(n^2)