Модуль "Прямой эфир" и мои поздравления сообществу))

Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = | A | . Для типичного алгоритма хорошее поведение — это O \left(n \log n \right)[1] и плохое поведение — это O \left(n^2 \right). Идеальное поведение для упорядочения — O \left(n \right). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в \Omega \left(n \log n \right) сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью O \left(n \cdot \log \log n \cdot \log \log \log n \right), использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О-обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за O \left(\log^2 n \right) операций. При этом число n должно быть заранее известно;
Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют O \left(\log n \right) памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет O \left(1 \right)). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.