0

Какой из алгоритмов наиболее оптимальный - O(n), O(log(n)) или O(n * log(n))?

1
  • 1
    Сложность алгоритма связана с его эффективностью как бы не напрямую - там всегда присутствует скрытая константа. Сложность позволяет оценить количество итераций, но ничего не говорит о времени и ресурсах на одну итерацию. Так что в реальности алгоритм с бОльшей формально сложностью может быть более эффективным. Только на гипер-больших объёмах можно более-менее гарантировать, что менее сложный алгоритм эффективнее - т.е. всегда есть точка, за которой менее сложный алгоритм начинает выигрывать, но она далеко не всегда в начале.
    – Akina
    23 авг 2018 в 6:47

2 ответа 2

5

Очевидно, что глобально O(log n) быстрее O(n), а тот быстрее O(n*log n). Но это теория :)

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

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

Словом, если вы рассматриваете проблему с теоретической точки зрения - то так, как я написал в первой строке.

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

4
  • можно еще графики показать
    – Grundy
    23 авг 2018 в 6:24
  • я не понял насчет локального и глобального
    – Randall
    23 авг 2018 в 6:25
  • @Избытоксусликов Глобально - значит, в самом общем случае, при суперогромных значениях N. Локально - для конкретных данных. Например, отсортировать практически отсортированный небольшой массив обычно быстрее вставками с O(n^2), чем чем-то с O(n lg n). Или - писать бинарный поиск для массива из нескольких элементов - никакого смысла...
    – Harry
    23 авг 2018 в 7:14
  • @Harry теперь понял спасибо добавил плюс :)
    – Randall
    23 авг 2018 в 7:25
2

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

Для примера вы можете взять несколько вариантов сортировок.

Допустим :

  • BubleSort
  • QuickSort
  • BinarySort
  • ShakeSort

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

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

Вот немного статей на предмет асимтотической сложности :

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.