Подсчет сортировки имеет нижнюю границу O (n)

Question

Время работы счетной сортировки Θ (n + k). Если k = O (n), алгоритм равен O (n). K представляет собой диапазон входных элементов. Могу ли я сказать, что сортировка Counting имеет нижнюю границу O (n), потому что алгоритму требуется O (n) времени для вычисления проблемы, и что нижняя граница O (n) показывает, что нет никакой надежды на решение конкретной задачи c задача вычисления по времени лучше, чем Ω (n) ??

Answer 1

Другой взгляд на то, почему нижняя граница действительно равна Ω (n): если вы хотите отсортировать массив из n элементов, вам нужно хотя бы посмотреть на все элементы массива. Если вы этого не сделаете, вы не сможете сформировать отсортированный список всех элементов массива, потому что вы не будете знать, что это за элементы массива. : -)

Это дает немедленную нижнюю границу Ω (n) для сортировки любой последовательности из n элементов, если только вы не можете прочитать несколько элементов последовательности одновременно (скажем, используя параллелизм или если элементы массива таковы). маленький, что вы можете прочитать несколько с помощью одной машинной инструкции.)

Answer 2

Ну да, поскольку T (n, k) = Theta (n + k), тогда T (n, k) = Omega (n + k). Поскольку k неотрицательно, мы знаем, что n + k = Omega (n), и поэтому T (n, k) = Omega (n), как требуется.