Перво-наперво: большое обозначение O - это классификация функций , символ O(n) обозначает множество всех функций от ℝ до ℝ, которые растут максимальнобыстро / почти как любое положительное кратное функции f (n) = n .
Это техническое введение (которое было сужено до этого контекста) было необходимо, чтобы прояснить, что нотация большого О используется для определения того, насколько быстро / сильно растет функция.
И при этом,мы не рассматриваем точное кратное число: 10n , 5n и 20n все равны O(n), потому что они кратны функции n.
В то время как такие вещи, как O(5n), немного злоупотребляют нотацией (где у нас есть несколько символов, обозначающих тот же набор, что и O(n)), они часто используются.
Для обозначения больших О нужна функция измерения. В теории вычислительной сложности двумя основными функциями являются: сложность времени и сложность пространства .
Сложность по времени - это функция, которая измеряет количество шагов , предпринятых алгоритмом для получения его выходных данных как функции длины кодировки его входа (то есть вход 10 как длина 2, две цифры).
Здесь есть скрытая ошибка, что такое шаг ?
Шаг является только шагомкогда дана вычислительная модель , другими словами, сначала нужно выяснить, как выполняются вычисления, какие шаги возможны.
Это редко разъясняется или явно указывается в литературе, я не знаюЗачем.
Например, инструкция a = b + c часто рассматривается как один шаг, потому что используемая вычислительная модель является языком высокого уровня, на котором написана программа.
Однако существуют ситуации, когдаa = b + c не считается единственным шагом, одним из таких контекстов является битовая сложность , модель, которая рассматривает каждую операцию на каждом бите в один шаг (таким образом, эта инструкция будет O(m), где mдлина в битах чисел).
В вашем примере первая реализация имеет сложность O(1), поскольку в теле функции есть только один оператор.
Второй имеет два оператора, один из которых является инициализацией переменной.Это зависит от вычислительной модели, чтобы установить, считаются ли переменные, инициализированные из константных выражений (будьте осторожны, если они берут свои значения из чего-то, что должно быть вычислено во время выполнения), как шаг или нет.
Можно смело предполагать, что они всегда делают, так как они добавляютсамое большее O(1) от общей стоимости, в которой будет доминировать любой код в теле функции (если тело функции не имеет только переменные инициализации).
Таким образом, вторая функция стоит O(2) (со злоупотреблением нотацией)но O(2) = O(1) по определению.
Это должно прояснить недоразумение о циклах процессора.При использовании языка высокого уровня для описания алгоритма, который нас не касается циклов ЦП, наша модель вычислений - это машина, которая понимает этот язык высокого уровня напрямую!Это должно иметь место, поскольку мы не можем знать, как это будет переводиться в инструкции по сборке, поэтому мы не можем считать циклы ЦП.
Помните время сложность составляет , а не о времени, которое мы измеряемТо есть речь идет о количестве шагов , а не о количестве прошедших тактов.
При использовании языка высокого уровня подразумевается, что вычислительная модель представляет собой шаг, в котором каждое утверждение языка является шагом.
Еще одно предостережение: сложность времени в сочетании с большой нотацией O не может использоваться для слишком точного измерения производительности.O(n^2) с небольшой константой лучше, чем O(n) с такой огромной константой, что она всегда будет больше, чем любое возможное значение n для любой реальной реализации проблемы.
Ноэто неудобство (чаще всего встречается в численных методах), для общего обзора константы можно отбросить. И действительно, это отличный инструмент, иначе анализ был бы слишком сложным.