Какой из алгоритмов наиболее оптимальный - O(n)
, O(log(n))
или O(n * log(n))
?
-
1Сложность алгоритма связана с его эффективностью как бы не напрямую - там всегда присутствует скрытая константа. Сложность позволяет оценить количество итераций, но ничего не говорит о времени и ресурсах на одну итерацию. Так что в реальности алгоритм с бОльшей формально сложностью может быть более эффективным. Только на гипер-больших объёмах можно более-менее гарантировать, что менее сложный алгоритм эффективнее - т.е. всегда есть точка, за которой менее сложный алгоритм начинает выигрывать, но она далеко не всегда в начале.– Akina23 авг 2018 в 6:47
2 ответа
Очевидно, что глобально O(log n)
быстрее O(n)
, а тот быстрее O(n*log n)
. Но это теория :)
Но локально могут быть разные входные данные, разные реализации - так что при реальной работе алгоритм с лучшей асимптотикой может показывать худшую производительность.
Не следует также забывать и о расходах, например, памяти - вполне может оказаться, что для более быстрого алгоритма просто не хватит памяти.
Словом, если вы рассматриваете проблему с теоретической точки зрения - то так, как я написал в первой строке.
С практической при выборе конкретного алгоритма - надо пробовать и замерять...
-
-
-
@Избытоксусликов Глобально - значит, в самом общем случае, при суперогромных значениях N. Локально - для конкретных данных. Например, отсортировать практически отсортированный небольшой массив обычно быстрее вставками с O(n^2), чем чем-то с O(n lg n). Или - писать бинарный поиск для массива из нескольких элементов - никакого смысла...– Harry23 авг 2018 в 7:14
-
Асимптотическая сложность алгоритма, как правило берется в самом худшем случае - объем работы на каждую единицу входных данных. Эта сложность как правило относительная, на практике все зависит от входных данных.
Для примера вы можете взять несколько вариантов сортировок.
Допустим :
- BubleSort
- QuickSort
- BinarySort
- ShakeSort
И в каждый из них по очереди скармливать 10 вариантов входных данных и какими либо StopWatch смотреть на время сортировки, и проследить зависимость данных сортировок по времени и по входным данным сравнивая каждый с другим типом сортировки.
Оговорюсь еще раз - все зависит от входных данных, могут быть случаи когда при идентичных входных данных, разные алгоритмы с разными асимтотическими сложностями показывают интересные результаты - алгоритм с дорогой сложность может проделать работу быстрее чем алгоритм с более дешевой сложность.
Вот немного статей на предмет асимтотической сложности :