сортировка выбором – это алгоритм сортировки, используемый для сортировки массива/списка.
Временная сложность
Временная сложность сортировки выбором составляет O(n²). то есть квадратичное время.
Объяснение
В сортировке выбором мы выполняем следующие операции:
- Сначала выберите элемент из списка
- Во-вторых, мы сравниваем этот элемент с другими оставшимися элементами в этом списке.
- Повторяйте первый шаг, пока список не станет пустым.
Итак, мы должны сначала выполнить шаг для каждого элемента в списке, и временная сложность для этого составляет O(n)
И затем мы должны сравнить этот элемент с другими оставшимися элементами в списке, и время сложность для этого O(n — z), где z — количество элементов, которые мы уже проверили, но, поскольку мы игнорируем константы в нотации Big O, поэтому вместо записи O (n — z) мы просто напишем это как O (н)
Таким образом, у нас есть временная сложность O(n * n) для всего алгоритма, которую мы также можем записать как O(n²).
