Асимптотический рост функций

Question

Как определить, находятся ли заданные значения f (n) и g (n) в тэте, омеге, большой ой, маленькой омеге или небольшой ой?- Я думаю, что один из способов сделать это - построить графики обеих функций f (n) и g (n).Даже при построении графиков, как мы говорим, когда af (n) находится в тэте, омеге, большой ой, маленькой омеге или маленькой ой?Не ясно по этому вопросу.Может кто-нибудь добавить более подробную информацию об этом?

Также я не уверен, что это правильный путь.Может кто-нибудь сказать мне, если есть какой-либо другой более простой способ сделать это.Скажем, пример: f (n) = sq root (n) и g (n) = n ^ sin n

Answer 1

Вы не определяете асимптотический рост, наблюдая за ним. Для каждого типа асимптотического отношения роста существуют формальные определения, которые точно и точно объясняют, что они означают. Вы определяете, соответствуют ли две функции заданному отношению, математически определяя, удовлетворяют ли они формальному определению отношения.

Например, одно из нескольких эквивалентных формальных определений для Big-O выглядит следующим образом:

f = O (g) тогда и только тогда, когда lim [n -> inf] (f (n) / g (n))

Так, например, если f (n) = n и g (n) = n ^ 2, вы можете заметить, что предел как n -> бесконечность n / n ^ 2 = 0, и поэтому f = О (г).

Или, если f (n) = n и g (n) = 2n, вы можете наблюдать это как n-> inf, n / 2n -> 1/2

Однако, если f (n) = n и g (n) = sqrt (n), вы можете заметить, что предел при n -> бесконечность n / sqrt (n) = бесконечность, поэтому f! = O ( г).

Ваш пример f и g сложен, потому что синус колеблется между -1 и 1 при увеличении n. Но Wolfram Alpha говорит мне, что рассматриваемый предел равен бесконечности, поэтому sqrt (n)! = O (n ^ (sin (n)).

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

Edit:

Кажется, вы ищете эмпирические правила. Вот быстрый и простой способ определить асимптотический порядок для относительно простых функций f и g. Рассмотрим наибольшую степень n в каждой функции:

• Если наивысшая мощность одинакова, то f = O (g), g = O (f), f = Омега (g), g = Омега (f), f = Тета (g), g = Тета (е)
• Если самая высокая мощность в f меньше, чем самая высокая мощность в g, то f = O (g), f = o (g), g = Омега (f), g = Омега (f)
• Если самая высокая мощность в f больше, чем самая высокая мощность в g, то f = Омега (g), f = Омега (g), g = O (f), g = o (f)

Конечно, если функции не являются многочленами от n или более сложны, и определить, каковы максимальные степени (например, ваш пример с использованием синуса), непросто, вам все равно придется вернуться к формальному определению.

Некоторые вещи, которые всегда верны:

• Тета по определению является соединением О и Омеги. f = O (g) ^ f = Омега (g) <=> f = Theta (g) [где ^ представляет логические "и"]
• "Маленькие" отношения на 1040 * сильнее , чем "большие" отношения. Это означает, что f = o (g) => f = O (g) и f = omega (g) => f = Omega (g), но обратные направления неверны.

Answer 2

Построение графика функций теоретически недостаточно.(Несмотря на то, что построение графика, а затем обоснование на основе этого может. Кроме того, практически, этого достаточно, если вы построите его для достаточно больших значений)

Правильный способ - построить доказательство:

Функция f(n) равна O(g(n)), если существуют положительные значения K и n0, такие что f(n) < K × g(x) для каждого n > n0.

Предположим, что это верно для f(n) = sqrt(n) и g(n) = n^sin n и некоторые K и n0.Теперь рассмотрим число n1, которое

1. больше этого n0
2. больше 1
3. больше K²
4. , для которого выполняется уравнение g(n1) = 1

Существует бесконечно много чисел, удовлетворяющих этим условиям: g(n1) = 1 при sin n1 = 0, то есть n1 = a × π для любого целого числа a,Ограничение их до n1 > max(n0, 1, K²) все еще оставляет бесконечно много возможностей, поэтому мы выбираем одну.

Итак, у нас есть g(n1) = 1.Какое значение f(n1)?Это sqrt(n1), что больше K (потому что n1 > K²).

Давайте соединим это: K < f(n1) < K × g(n1) = K, другими словами K < K, что не может быть правдой, это означаетисходное предположение неверно и поэтому f(n) != O(g(n)).

Answer 3

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

В простом случае вы можете сосчитать вложенные циклы, чтобы понять, как долгобрать.Если у вас есть цикл от 1 до n внутри цикла от 1 до t, и единственные функции, вызываемые внутри, занимают постоянное время (или вы просто выполняете арифметические операции внутри, скажем), то это Theta (nt).Если вы знаете, что t <= n, это также O (n <sup>2 ).

В более сложных случаях вам может понадобиться Основная теорема илиподобное, аналогичное, похожее.В некоторых случаях может быть очень сложно (на уровне исследования) определить сложность!

Answer 4

Вот как вы вычисляете Big-O для заданных f (n) и g (n) с использованием пределов.

Построение функций для больших значений x как f (x), так и g (x) на одном и том же наборе осей должно помочь вам сразу определить асимптотику.