Сложность в алгоритмах

Question

Я читал эту страницу https://www.toptal.com/developers/sorting-algorithms, и один из моментов, которые они хотели сфокусировать, был следующим:

"Покажите, что асимптотическое поведение в худшем случае не всегда является решающим фактором при выбореалгоритм. "

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

Answer 1

Взять Hashtables в качестве примера.Как правило, они очень быстрые и вставка, поиск, удаление должны работать в постоянное время, и это здорово.Вот почему каждый использует их.Однако в худшем случае хэш-значение каждого из ваших элементов будет одинаковым, и тогда время выполнения станет намного хуже.Есть способы минимизировать ущерб, такой как хеширование Cuckoo и т. Д., Но в худшем случае хеш-таблица будет иметь худшее время выполнения или худшее потребление памяти, чем другие структуры данных.Обычно вы не выбираете Hashtables из-за их асимптотического времени выполнения в худшем случае, потому что это очень маловероятно.

Редактировать: Извините, я пропустил вопрос об алгоритмах, а не об общей сложности времени выполнения.Но мне просто нужно небольшое изменение: предположим, вы хотите, чтобы алгоритм нашел все дубликаты в массиве.Вы можете просто вставить все элементы в HashSet.Если у вас есть хорошая функция хеширования, обычно у вас будут только коллизии, если ваши элементы одинаковы.Таким образом, у вас будет O (N) время выполнения.Но если вы получаете много ложных срабатываний, когда элементы имеют одинаковое значение хеш-функции, даже если они различаются, ваш алгоритм findDuplicates будет переходить в квадратичное время выполнения.Опять же, такое столкновение очень маловероятно, поэтому вы, вероятно, в любом случае воспользуетесь этим подходом.

Answer 2

В реальном мире K и M также являются основным фактором, например, анимация не учитывает эти факторы.K - постоянный фактор в алгоритме, а M - стоимость памяти.

Это причина того, что Quicksort используется в основном везде, потому что у них не только хорошее среднее значение, но среднее значение очень низкое K & M,

Но тогда вам нужно смягчить проблему, которая в худшем случае все еще довольно плоха, используйте алгоритм отката, такой как Introsort , если рекурсия слишком глубокая, вернитесь к сортировке кучи иликогда количество значений становится низким, переключитесь на сортировку вставкой.

Answer 3

Часто возникают проблемы, для которых один алгоритм обычно быстрее, чем другой алгоритм, но для которого наихудший случай асимптотически медленнее.В частности, один алгоритм может быть быстрее для конкретных данных, с которыми вы работаете, даже если в худшем случае он асимптотически медленнее.Использование памяти также может быть проблемой в некоторых случаях.Хорошим примером этого является быстрая сортировка против сортировки слиянием.Они оба имеют среднее время выполнения O (n log n), но быстрая сортировка обычно быстрее.Однако в наихудшем случае быстрая сортировка имеет время выполнения O (n ^ 2).Кроме того, для слияния традиционно требуется O (n) дополнительной памяти.Есть вариант на месте, но я думаю, что он значительно медленнее.Еще одно соображение заключается в том, что сортировку слиянием легче распараллелить.

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