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

Question

Учитывая этот алгоритм сортировки, как вы выражаете его временную сложность?

Первоначально представлен здесь (частичный архив) .

#!/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

Answer 1

O(max(input)+n)

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

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

Answer 2

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

Answer 3

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

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

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

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

Answer 4

И временная сложность, и сложность этого алгоритма составляют O(braindead).

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

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

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

Сложность времени в данном случае не имеет значения. Вы не можете получить менее оптимизированным, чем «неправильно».

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

Answer 5

Я с Джорданом, за исключением того, что я думаю, что сложность настенных часов лучше выражать в виде O (2 ^ m), где m - размер каждого элемента, а не O (max (input)).

Если каждый элемент имеет размер m, самый большой элемент будет иметь целочисленное значение 2 ^ m (минус один, но это никого не волнует). По построению алгоритм требует, чтобы время установки было меньше 1, константы.

То есть сложность настенного времени O (2 ^ m), сложность подсчета операций 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).

Answer 6

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

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

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

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

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

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

Answer 7

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