Почему O(n!) медленнее O(n^2)?

Question

Изучаю пособие "Грокаем Алгоритмы", здесь написано следующее:

O(n!). Пример: очень медленные алгоритмы.
O(n^2). Пример: медленные алгоритмы.

Для себя решил проверить.

O(n!), n! = 3! => O(3!) = 1 * 2 * 3 = 6
O(n^2), n = 3 => O(3^2) = 3 * 3 = 9

Следовательно O(n!) < O(n^2)

Из сего можно сделать вывод: O(n!) быстрее, чем O(n^2)

Или я что-то не так понял?

Answer 1

Дело в том, что значок O() обозначает "асимптотически".

То есть, чтобы понять, почему O(n!) медленнее O(n^2), надо написать рядом несколько значений каждой из функций:

    n        n!          n^2
    1        1           1
    2        2           4
    3        6           9
    4        24          16
    5        120         25
    6        720         36
    7        5040        49
    8        40320       64
    9        362880      81
    10       3628800     100

Так понятнее?

PS. А книжка - да, прикольная. Особенно приятно, что она объясняет алгоритмы типа BFS простыми словами, без лишнего заморачивания головы

Answer 2

О большое - асимптотическое поведение функции при параметре стремящемся к бесконечности

конечно n^2 на некотором участке больше n!, но при больших n n! значительно больше n^2

но опять же всегда есть свои тонкости:

например пример умножения матриц - классический способ имеет сложность O(n^3), а самый быстрый из известных алгоритмов имеет сложность O(n^2.3727) (Алгоритм Копперсмита — Винограда), т.е. лучше использовать последний алгоритм, как более быстрый

однако это именно ассимптотические оценки и скорости двух алгоритмов лишь пропорциональны данным степеням (3 и 2.3727), т.е. для первого алгоритма скорость может быть

v1 = 1000 * n^3

а для второго

v2  = 1000000 * n^2.3727

в итоге асимптотически более быстрый алгоритм почти для всех задач умножения матриц будет медленнее

например при сжатии jpeg выполняется много операций умножения матриц 8x8 и самый быстрый алгоритм - это классический O(n^3), причем алгоритм выглядит не как какие-то вложенные циклы от 0 до 7, а как 512 строчек умножения и сложения элементов массива (не рассматриваю конечно специализированные возможности современных процессоров)

чаше всего в алгоритмах та самая n довольно большая и поэтому можно ориентироваться на эту оценку, но иногда бывают и исключения

например: бинарный поиск по отсортированному списку имеет сложность O(log(N)), а обычный поиск по неотсортированному списку O(N), то если у вас массивчик из 3 элементов, то никакого бинарного поиска не нужно - значительно больше работать будет

БЛОГ НА HUSL

Почему O(n!) медленнее O(n^2)?

Ответы (2 шт):