Экспоненты: Little Oh

Question

Что интуитивно означает n^b = o (aⁿ) (o - маленький oh)? Я только начинаю самостоятельно учить свои собственные алгоритмы, и мне трудно интерпретировать такие выражения каждый раз, когда я их вижу. Здесь, как я понял, для функции n^b скорость роста равна aⁿ. Но это не имеет смысла для меня, независимо от того, прав он или нет.

Answer 1

(Для простоты я предполагаю, что все функции всегда возвращают положительные значения. Это имеет место, например, для функций, измеряющих время выполнения алгоритма, поскольку ни один алгоритм не запускается за "отрицательное" время.)

---

Во-первых, краткий обзор нотации big-O, чтобы прояснить общее недопонимание:

Чтобы сказать это f является O(g) Значит это f растет асимптотически максимум так быстро, как g, Более формально, рассматривая оба f а также g как функции переменной n, чтобы сказать это f(n) является O(g(n)) означает, что есть постоянная Kтак что в конце концов, f(n) < K * g(n), Слово "в конце концов" здесь означает, что есть некоторое фиксированное значение N (который является функцией K, f, а также g), так что если n > N затем f(n) < K * g(n),

Например, функция f(n) = n + 2 является O(n^2), Чтобы понять почему, пусть K = 1, Тогда, если n > 10, у нас есть n + 2 < n^2, поэтому наши условия выполнены. Несколько вещей, на которые стоит обратить внимание:

• За n = 1, у нас есть f(n) = 3 а также g(n) = 1, так f(n) < K * g(n) на самом деле не удается. Это нормально! Помните, что неравенство нужно только выполнить в конце концов, и не имеет значения, если неравенство терпит неудачу для некоторого небольшого конечного списка n,
• Мы использовали K = 1, но нам не нужно было Например, K = 2 также работал бы. Важно то, что есть некоторая ценность K что дает нам неравенство, которое мы хотим в конце концов.
• Мы видели это n + 2 является O(n^2), Это может выглядеть странно, и вы можете сказать: "Подождите, не n + 2 на самом деле O(n)"Ответ - да. n + 2 является O(n), O(n^2), O(n^3), O(n/3), так далее.

---

Little-o нотация немного отличается. Обозначение Big-O, интуитивно, говорит, что если f является O(g), затем f растет асимптотически максимум так быстро, как g, Литл-о обозначение говорит, что если f является o(g), затем f растет асимптотически строго медленнее, чем g,

Формально, f является o(g) если для любого (скажем, положительного) выбораKв конечном итоге неравенство f(n) < K * o(g) держит. Так, например:

• Функция f(n) = n не o(n), Это потому, что для K = 1нет значения n чтобы f(n) < K * g(n), Наглядно, f а также g расти асимптотически с той же скоростью, так f не растет строго медленнее, чем g делает.
• Функция f(n) = n является o(n^2), Почему это? Выберите ваше любимое положительное значение K, (Чтобы увидеть актуальную точку, попробуйте сделать K маленький, например 0,001.) Представьте себе график функций f(n) а также K * g(n), Один из них - прямая линия, проходящая через начало положительного склона, а другой - вогнутая парабола, проходящая через начало координат. В конце концов парабола будет выше линии и останется такой. (Если вы помните свой предварительный расчет / исчисление...)

---

Теперь перейдем к вашему актуальному вопросу: пусть f(n) = n^b а также g(n) = a^n, Вы спросили почему f является o(g),

Предположительно, автор оригинального высказывания относится к a а также b как постоянные, положительные действительные числа, и более того a > 1 (если a <= 1 тогда утверждение ложно).

Утверждение на английском языке:

Для любого положительного действительного числа bи любое действительное число a > 1, функция n^b растет асимптотически строго медленнее, чем a^n,

Это важно знать, если вы когда-нибудь будете иметь дело с алгоритмической сложностью. Проще говоря, можно сказать, что "многочлены растут намного медленнее, чем экспоненциальные функции". Не сразу очевидно, что это правда, и это слишком много, чтобы написать, поэтому вот ссылка:

https://math.stackexchange.com/questions/55468/how-to-prove-that-exponential-grows-faster-than-polynomial

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

Удачи!

Answer 2

Сверхвысокое значение выражения n^b - это o (aⁿ) просто то, что экспоненциальные функции, такие как a^n, растут намного быстрее, чем полиномиальные функции, такие как n^b.

Важная вещь, которую нужно понять, глядя на большие О и маленькие нотации, состоит в том, что они оба являются верхними границами. Я предполагаю, что именно поэтому ты запутался. n^b является o (aⁿ), потому что скорость роста aⁿ намного больше. Вы могли бы, вероятно, найти более тесную верхнюю границу на n^b (ту, где промежуток между границей и функцией меньше), но aⁿ все еще действителен. Также вероятно стоит посмотреть на разницу между Big O и Little O.

Помните, что функция f является Big O функции g, если для некоторой константы k > 0 вы можете в конечном итоге найти минимальное значение для n, так что f(n) ≤ k * g(n).

Функция f мало о функции g, если для любой константы k > 0 вы можете в конечном итоге найти минимальное значение для n, так что f(n) ≤ k * g(n).

Обратите внимание, что выполнить небольшое требование o труднее, а это означает, что если функция f является маленькой функцией o, то она также является Big O g, и это означает, что функция g растет быстрее, чем если бы она была просто Big O g,

В вашем примере, если b равно 3, а a равно 2, и мы устанавливаем k в 1, мы можем определить минимальное значение для n, чтобы n^b ≤ k * aⁿ. В этом случае это между 9 и 10, так как9³ = 729 а также 1 * 2⁹ = 512, что означает, что в 9 aⁿ еще не больше, чем n^b, но10³ = 1000 а также 1 * 2¹⁰ = 1024, что означает, что ⁿ теперь больше, чем n^b. Вы можете увидеть на графике эти функции, что ⁿ будет больше, чем n^b, для любого значения n > 10. На данный момент мы только показали, что n^b - это Big O для ⁿ, поскольку Big O требует этого только для некоторого значения k > 0 (мы выбрали 1) aⁿ ≥ n^b для некоторого минимума n (в данном случае это между 9 и 10)

Чтобы показать, что n^b меньше o изⁿ, мы должны показать, что для любого k, большего 0, вы все равно можете найти минимальное значение n, так что aⁿ > n^b. Например, если вы выбрали k = .5, минимум 10, который мы нашли ранее, не работает, так как 10³ = 1000, а также .5 * 2¹⁰ = 512, Но мы можем просто продолжать сдвигать минимум для n дальше и дальше, чем меньше вы делаете k, тем больше минимум для n будет b. Сказать, что n^b - это меньшее o из^n, значит, независимо от того, как мало вы делаете k, мы всегда сможем найти достаточно большое значение для n, так что n^b ≤ k * aⁿ

Answer 3

f(n)=o(g(n)) Значит это f(n)/g(n)->0 когда n->infinite,

Для вашей проблемы, он должен держать a>1, (n^b)/(a^n)->0 когда n-> бесконечный, так как (n^b)/(sqrt(a)^n*sqrt(a)^n))=((n^b)/sqrt(a)^n) * (1/sqrt(a)^n), Позволять f(n)=((n^b)/sqrt(a)^n) сначала функция увеличивается, а затем уменьшается, так что вы можете получить максимальное значение max(f(n))=M, затем (n^b)/(a^n) < M/(sqrt(a)^n), поскольку a>1, sqrt(a)>1, так (sqrt(a)^n)->infinite когда n->infinite, То есть M/(sqrt(a)^n)->0 когда n->infinite, Наконец, мы получаем (n^b)/(a^n)->0 когда n-> бесконечный. То есть n^b=o(a^n) по определению.