Учитывая этот алгоритм сортировки, как вы выражаете его временную сложность?
Первоначально представлены здесь (частичный архив).
#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shift
done
wait
example usage:
./sleepsort.bash 5 3 6 3 6 3 1 4 7
Я думаю, что paxdiablo ближайший, но не по правильной причине. Сложность времени игнорирует проблемы на реальном оборудовании, такие как размеры кеша, пределы памяти и в этом случае ограниченное количество процессов и работу планировщика.
На основе страницы Википедии для временной сложности Я бы сказал, что вы не можете определить сложность выполнения, потому что если она определяется как:
Сложность времени обычно оценивается путем подсчета количества элементарных операций, выполняемых алгоритмом, где элементарная операция занимает фиксированное количество времени для выполнения. Таким образом, количество времени и количество элементарных операций, выполняемых алгоритмом, отличаются не более чем постоянным фактором.
Тогда мы не можем говорить о сложности выполнения этого алгоритма, потому что время, которое выполняются элементарными операциями, значительно отличается от того, что принятое время будет отличаться более чем постоянным фактором.
O(max(input)+n)
Сложность выглядит просто неудобно, поскольку большинство алгоритмов сортировки являются агностическими данными. Их время масштабируется с объемом данных, а не с данными.
FWIW, как указано здесь, это не надежный алгоритм сортировки данных.
Один вопрос, который, по-видимому, никто не рассмотрел, - это то, как эти sleep реализованы. В конечном итоге они оказываются где-то в планировщике, а операционная сложность будет зависеть от используемого алгоритма планирования. Например, если sleep помещаются как события в очередь приоритетов, вы, скорее всего, получите что-то, что эквивалентно heapsort, со сложностью O (n log n). Наивный алгоритм планирования может привести к O (n ^ 2).
Как сложность времени, так и сложность процесса для этого алгоритма O(braindead).
При достаточно большом значении в наборе данных вы будете ждать ответа до тех пор, пока солнце не взорвется.
При достаточно большом размере набора данных вы будете
(2,9,9,9,9,9,...,9,9,1) не будет правильно сортировать 1 и 2.В этом случае сложность времени не имеет значения. Вы не можете быть менее оптимизированы, чем "неправильные".
Хорошо использовать анализ сложности для сравнения алгоритмов с изменением размера набора данных, но не тогда, когда алгоритмы нелепые в первую очередь: -)
Если вы прочитаете нить, вы увидите, что на ваш вопрос уже ответили. Сложность времени O(max(input)) и операционная сложность (количество операций) O(n).
Хотя выглядит линейно, я думаю, что сложность по-прежнему равна O (log (n) * max (input)).
Когда мы говорим об асимптотической сложности времени, это означает, сколько времени занимает, когда n растет бесконечно большим.
Алгоритм сортировки на основе сравнения не может быть быстрее, чем O (n * log (n)), а Sleep-Sort на самом деле основан на сравнении:
Процессы засыпают n секунд и пробуждаются. ОС должна найти наименьшее оставшееся время сна из всего процесса сна и разбудить его, если это будет время.
Для этого потребуется очередь приоритетов, которая принимает время O (logN), вставляя элемент, и O (1) находит минимальный элемент, а O (logN) удаляет минимальный элемент.
Когда n становится очень большим, для пробуждения процесса потребуется более 1 секунды, что делает его больше, чем O (n).
Я с Иорданией, за исключением того, что, по-моему, сложность настенных часов лучше выражается как O (2 ^ m), где m - размер каждого элемента, а не O (max (вход)).
Если каждый элемент имеет размер m, наибольший элемент будет иметь целочисленное значение 2 ^ m (минус один, но об этом никто не заботится). По построению алгоритм требует, чтобы время настройки было меньше 1, константы.
Таким образом, сложность настенного времени O (2 м), сложность счетчика операций O (n).
Измененный алгоритм с учетом времени установки, скорее всего, будет иметь сложность времени по шкале O (2 ^ m + n). Например, он мог бы отметить текущее время в начале, вычислить base_time = start_time + k*len(list) (для некоторой подходящей константы k), а затем потоки спящего до времени base_time+i. Тогда k*len(list), очевидно, O (n) и i равно O (2 ^ m), как и раньше, для всего O (2 ^ m + n).