Алгоритмы сортировка. O(n log n) - что означает каждая буква в этой формуле и как это пояснить? O(n+k) - и в этой тоже.

Question

Алгоритмы сортировка. O(n log n) - что означает каждая буква в этой формуле и как это пояснить? O(n+k) - и в этой тоже.

Валерия Профи (801), закрыт 14 лет назад

Answer 1

n - количество элементов
O(n log n) - Значит, что сложность пропорциональна n log n - скорее всего - имеется в виду какая-либо сортировка основанная на попарном сравнении ключей. Например - "быстрая сортировка" или построение бинарного дерева.
Например, для сортировки 100 элементов потребуется ~700 условных единиц времени. (100 * log(100))

O(n+k) - пропорционально n+k

Answer 2

Это характеристика алгоритма, называют временем выполнения алгоритма. Чем меньше, тем лучше. n - количество элементов для сортировки. О - это оценка, можно считать что просто константа.