Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиПоискОблакоVK ComboВсе проекты

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

Валерия Профи (801), закрыт 12 лет назад
Лучший ответ
Мужик С Веслом Оракул (80110) 12 лет назад
n - количество элементов
O(n log n) - Значит, что сложность пропорциональна n log n - скорее всего - имеется в виду какая-либо сортировка основанная на попарном сравнении ключей. Например - "быстрая сортировка" или построение бинарного дерева.
Например, для сортировки 100 элементов потребуется ~700 условных единиц времени. (100 * log(100))

O(n+k) - пропорционально n+k
Остальные ответы
Cooler Мастер (1063) 12 лет назад
Это характеристика алгоритма, называют временем выполнения алгоритма. Чем меньше, тем лучше. n - количество элементов для сортировки. О - это оценка, можно считать что просто константа.
Похожие вопросы