Как f (n)

Question

Я читал Это руководство по времени сложности , и я немного озадачен своим объяснением большого $ O $ Обозначения. Пишет:

$ o (g (n))= $ { $ f (n) $ : там Существуют положительные константы $ C $ и $ n_0 $ такое, что $ 0 \ leq f (n) \ leq c * g (n) $ для всех $ n> n_0 $ .

То, как я это понимаю, $ C * G (n) $ обозначает $ C $ умноженный по $ g (n) $ . Если это так, то как вышеуказанное выражение указывает время, а не только что $ C * G (N) $ больше, чем $ f (n) $ ? Или я неправильно, и это некоторая запись, которую я не понимаю? Мое понимание временной сложности очень варьируется, поэтому простите меня, если это просто глупость на моей части.

Answer 1

Как f (n)

Это не так. Обозначение Бахманн-Ландау - это просто удобный способ сравнить скорость роста функций. Это ничего не говорит о , какие эти функции означают , и мы можем быть уверены, что Бахманн не думал о компьютерах, когда он придумал его в 1894 году.

Что означает вы назначаете эти функции, зависит от вас. Например, при анализе алгоритмов сортировки на основе сравнения мы обычно принимаем $ N $ , чтобы быть количеством элементов в коллекции и $ f (n) $ - это количество сравнений, или количество свопов, или количество сравнений и свопок.

Примечание также, что все это всегда относительно модели машины или модели затрат.

Как очень простой пример, если бы я спросил вас, что такое сложность шага в худшем случае алгоритмии для копирования списка, вы бы сказали $ O (N) $ . Но на самом деле, то правильный ответ будет "я не могу сказать вам, что, поскольку вы не указали машинную модель". Поскольку, например, в Turging Machine, копирование списка - $ O (N ^ 2) $ , потому что для каждого элемента скопирован, глава TM имеет Чтобы проехать дальше и дальше и дополнительно достичь конца списка, чтобы написать следующий элемент.

Answer 2

Сказать, что время работы алгоритма в $ O (G (N)) $ дает, как вы отмечали, только верхняя граница. Кроме того, верхняя граница дана с константами $ C $ и $ n_0 $ неизвестен. Так что да, это довольно слабая информация о времени работы.

Неуказанная константа $ C $ может содержать информацию о реальной стоимости основных операций алгоритма, которая может быть неизвестна и / или переменной между прогонами, Но все еще известно, что стоит ограничить время, которое ограничено. Неуказанная константа $ n_0 $ отражает, что связанные данные относится к большим размерам входа (или любой параметр $ n $ < / span> представляет).

Другие символы используются для предоставления других типов или более точная информация о времени работы.