Big-O - скорость роста функции

Question

Я хотел бы знать больше о Big-O и нашел этот кусок информации:

«, если f(x) = O(g(x)) темпы роста f(x) асимптотически меньше или равно скорость роста g(x) '

Что означает асимптотически в данном случае сценарий? Также мне трудно понять, почему Big-Theta не зависит от компьютера, который мы используем? Может ли кто-нибудь указать дополнительную информацию по этим двум вопросам?

Answer 1

Термин «асимптотически» в этом контексте относится к «как x переходит в бесконечность». Когда кто-то говорит, что «f (x) растет асимптотически медленнее, чем g (x),« они означают, что при очень больших значениях x функция g (x) будет расти быстрее, чем функция f (x). Это означает, что при достаточно больших х до тех пор, пока f (x) ≥ 1 и g (x) ≥ 1, значение g (x) всегда будет в конечном итоге больше, чем функция f (x).

Что касается этого вопроса:

Также у меня есть некоторые трудно понять, почему не Big-Theta зависит от компьютера, который мы используем?

Хотя O, Θ и Ω нотации широко используются в CS для описания среды выполнения, что это на самом деле не то, что они означают. Технически эти обозначения используются для количественной оценки темпов роста функций, независимо от того, что эти функции фактически означают. Например, вы найдете нотацию большого О, используемую в Stirling's approximation в дискретной математике, которая оценивает ln n! как n ln n - n + O (log n), где O (log n) означает «некоторая функция, скорость роста которой равна O (log n)». В CS, когда мы говорим, что алгоритм O (n), что это действительно означает, «функция, описывающая время выполнения этой функции, - это O (n)». Более корректно вы увидите выражения типа «время выполнения алгоритма: O (n)» или «алгоритм занимает время O (n)», подчеркивая, что нотация большого вывода используется для описания времени выполнения алгоритма, чем сам алгоритм. В этом смысле один ответ на ваш вопрос: «Почему запись Θ зависит от компьютера?» «Θ нотация только количественно определяет темпы роста функций и не имеет ничего общего с компьютерами».

В другом смысле, причина, почему конкретный компьютер не имеет значения, что Θ обозначение говорит о асимптотическим автономной работы, а не абсолютные Runtimes. Если алгоритм имеет время выполнения Θ (n), это означает, что время выполнения алгоритма масштабируется как некоторая линейная функция. Время выполнения этого алгоритма в качестве размера ввода может фактически быть чем-то вроде 100n + 137 или 20,000,000n-15, потому что все, что имеет значение, - это способ, которым эти среды выполнения работают, а не сами рабочие среды. Если вы запускаете тот же код на разных компьютерах, может потребоваться больше или меньше времени для запуска в зависимости от выбранного компьютера, но почти наверняка он не изменится от линейного масштабирования до масштабирования квадратично. Это означает, что асимптотически, время работы такое же, хотя абсолютно время работы может отличаться.

Надеюсь, это поможет!