Порядок вычислительной сложности - PullRequest
Новая
       91

Порядок вычислительной сложности

0 голосов
/ 28 февраля 2019

У меня около 8 алгоритмов с различной временной сложностью, и я хотел бы знать их порядок от самого медленного до самого быстрого. 

(Algorith1) O(n^3)
(Algorith2) O(1)
(Algorith3) O(log(n) + n)
(Algorith4) O(nlog(n))
(Algorith5) O(log(n))
(Algorith6) O(n^2 + nlog(n))
(Algorith7) O(n!)
(Algorith8) O(2^n)

Я знаю, что самая низкая и самая низкая производительность - O (n!) но что будет дальше от всего остального.

1 Ответ

0 голосов
/ 05 марта 2019

Не графите их и проверьте на Big-O!Асимптотическая сложность не так проста, вам нужно учесть все возможные константы впереди и быть добавленными (например, O (100n + log (n) по-прежнему эквивалентно O (n)). Все это, как говорится, для достаточно большихn и произвольная константа впереди: 

O(1) << O(log(n)) << O(log(n) + n) << O(nlog(n)) << O(n^2 + nlog(n)) << O(n^3) << O(2^n) << O(n!)
...