O(n*log(n)) и минимальная сложность алгоритмов сортировки
Изучив базовые алгоритмы сортировки (пузырьком, слиянием, быстрая и т.д.), мы обычно запоминаем, что временная сложность эффективной сортировки - O(n*log(n)). Но в один прекрасный момент мы встречаем, например, поразрядную сортировку и узнаём, что её временная сложность O(n*k), где k (в данном случае количество разрядов) - фиксированное значение для заданного множества элементов. Что делает поразрядную сортировку особенной? И что объединяет большинство остальных алгоритмов сортировки? Сравнение элементов (в поразрядной сортировке его нет). Именно сравнение элементов определяет минимальную временную сложность любого соответствующего алгоритма - Ω(n*log(n))...