Какова временная сложность сортировки сна?

Ответ 1

Я думаю, что paxdiablo ближайший, но не по правильной причине. Сложность времени игнорирует проблемы на реальном оборудовании, такие как размеры кеша, пределы памяти и в этом случае ограниченное количество процессов и работу планировщика.

На основе страницы Википедии для временной сложности Я бы сказал, что вы не можете определить сложность выполнения, потому что если она определяется как:

Сложность времени обычно оценивается путем подсчета количества элементарных операций, выполняемых алгоритмом, где элементарная операция занимает фиксированное количество времени для выполнения. Таким образом, количество времени и количество элементарных операций, выполняемых алгоритмом, отличаются не более чем постоянным фактором.

Тогда мы не можем говорить о сложности выполнения этого алгоритма, потому что время, которое выполняются элементарными операциями, значительно отличается от того, что принятое время будет отличаться более чем постоянным фактором.

Ответ 2

O(max(input)+n)

Сложность выглядит просто неудобно, поскольку большинство алгоритмов сортировки являются агностическими данными. Их время масштабируется с объемом данных, а не с данными.

FWIW, как указано здесь, это не надежный алгоритм сортировки данных.

Ответ 3

Один вопрос, который, по-видимому, никто не рассмотрел, - это то, как эти sleep реализованы. В конечном итоге они оказываются где-то в планировщике, а операционная сложность будет зависеть от используемого алгоритма планирования. Например, если sleep помещаются как события в очередь приоритетов, вы, скорее всего, получите что-то, что эквивалентно heapsort, со сложностью O (n log n). Наивный алгоритм планирования может привести к O (n ^ 2).

Ответ 4

Как сложность времени, так и сложность процесса для этого алгоритма O(braindead).

При достаточно большом значении в наборе данных вы будете ждать ответа до тех пор, пока солнце не взорвется.

При достаточно большом размере набора данных вы будете

• (1) ударил ваш лимит процесса; и
• (2) найдите, что ранние сны закончатся до того, как начнутся последние, что означает, что набор (2,9,9,9,9,9,...,9,9,1) не будет правильно сортировать 1 и 2.

В этом случае сложность времени не имеет значения. Вы не можете быть менее оптимизированы, чем "неправильные".

Хорошо использовать анализ сложности для сравнения алгоритмов с изменением размера набора данных, но не тогда, когда алгоритмы нелепые в первую очередь: -)

Ответ 5

Если вы прочитаете нить, вы увидите, что на ваш вопрос уже ответили. Сложность времени O(max(input)) и операционная сложность (количество операций) O(n).

Ответ 6

Хотя выглядит линейно, я думаю, что сложность по-прежнему равна O (log (n) * max (input)).

Когда мы говорим об асимптотической сложности времени, это означает, сколько времени занимает, когда n растет бесконечно большим.

Алгоритм сортировки на основе сравнения не может быть быстрее, чем O (n * log (n)), а Sleep-Sort на самом деле основан на сравнении:

Процессы засыпают n секунд и пробуждаются. ОС должна найти наименьшее оставшееся время сна из всего процесса сна и разбудить его, если это будет время.

Для этого потребуется очередь приоритетов, которая принимает время O (logN), вставляя элемент, и O (1) находит минимальный элемент, а O (logN) удаляет минимальный элемент.

Когда n становится очень большим, для пробуждения процесса потребуется более 1 секунды, что делает его больше, чем O (n).

Ответ 7

Я с Иорданией, за исключением того, что, по-моему, сложность настенных часов лучше выражается как 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).