Яка різниця між Big-O позначення O(n) і Little-O позначення o(n)?
Відповіді:
337 за відповідь № 1f ∈ O (g), по суті
Для принаймні один вибір постійної к > 0, можна знайти константу a таке, що для всіх x> a виконується нерівність 0 <= f (x) <= k g (x).
Зауважимо, що O (g) - множина всіх функцій, для яких виконується ця умова.
f ∈ o (g), по суті
Для кожен вибір постійної к > 0, можна знайти константу a таке, що для всіх x> a виконується нерівність 0 <= f (x) <k g (x).
Знову відзначимо, що o (g) - це набір.
У Big-O потрібно лише знайти певний множник к для яких нерівність не перевищує мінімуму х.
У Little-o має бути мінімум х після чого нерівність виконується незалежно від того, наскільки мала вона к, якщо він не є негативним або нульовим.
Ці обидва описують верхню межу, хочадещо протилежно, Little-o є сильнішим твердженням. Існує набагато більший розрив між темпами зростання f і g, якщо f ∈ o (g), ніж у випадку, якщо f ∈ O (g).
Однією з прикладів такої невідповідності є: f ∈ O (f) істинно, але f ∈ o (f) є помилковим. Отже, Big-O можна читати як "f ∈ O (g) означає, що асимптотичний ріст f" не перевищує g "s", тоді як "f ∈ o (g) означає, що асимптотичний ріст f" суворо повільніше ніж g "s". Це як <= проти <.
Більш конкретно, якщо значення g (x) є постійним кратним значенням f (x), то f ∈ O (g) істинно. Ось чому ви можете скидати константи під час роботи з нотацією big-O.
Проте, якщо f ∈ o (g) істинним, то g повинен включати вищу влада x у його формулі, і тому відносне поділ між f (x) і g (x) має фактично збільшуватися, оскільки x стає більше.
Використовувати суто математичні приклади (а не посилання на алгоритми):
Для Big-O справедливо наступне, але це не так, якби ви використовували мало-o:
- x² ∈ O (x²)
- x² ∈ O (x² + x)
- x² ∈ O (200 * x²)
Для мало-о:
- x² ∈ o (x³)
- x² ∈ o (x!)
- ln (x) ∈ o (x)
Зауважимо, що якщо f ∈ o (g), то випливає f ∈ O (g). напр. x² ∈ o (x³), так що також справедливо, що x² ∈ O (x³), (знову ж думайте про O <= і o як <)
160 за відповідь № 2
Біг-О - це як мало ≤ це до <. Big-O є включною верхньою межею, тоді як мало-o - сувора верхня межа.
Наприклад, функція f(n) = 3n це:
- в
O(n²),o(n²), іO(n) - не в
O(lg n),o(lg n), абоo(n)
Аналогічно число 1 це:
≤ 2,< 2, і≤ 1- ні
≤ 0,< 0, або< 1
Ось таблиця, що показує загальну ідею:
(Примітка: таблиця є гарним керівництвом, але визначення її межі має бути в термінах верхня межа замість нормальної межі. Наприклад, 3 + (n mod 2) коливається від 3 до 4 назавжди. Це в O(1) незважаючи на те, що не має нормальної межі, тому що вона все ще має a lim sup: 4.)
Я рекомендую запам'ятовувати, як нотація Big-O перетворюється на асимптотичні порівняння. Порівняння легше запам'ятовувати, але менш гнучкі, тому що ви не можете сказати такі речі, як nO (1) = P.
29 для відповіді № 3
Я знаходжу це, коли я не можу концептуально зрозуміти щось, про що думають чому можна використовувати X корисно зрозуміти X. (Не скажу, що ви не спробували цього, я просто встановлюю сцену.)
[матеріал, який ви знаєте] Загальний спосіб класифікаціїАлгоритми за часом виконання, і, посилаючись на велику-О складність алгоритму, ви можете отримати досить хорошу оцінку, яка з них "краще" - в залежності від того, що має "найменшу" функцію в О! Навіть у реальному світі O (N) є "кращим", ніж O (N²), забороняючи нерозумні речі, такі як супермасивні константи тощо. [/ Stuff ви знаєте]
Скажімо, існує деякий алгоритм, який виконується в O (N). Дуже добре, так? Але скажімо вам (ви, геніальна людина, ви) придумали алгоритм, який виконується в O (N/loglogloglogN). YAY! Його швидше! Але ви будете дурно писати це знову і знову, коли будете писати дисертацію. Таким чином, ви пишете це один раз, і ви можете сказати: "У цій роботі я довів, що алгоритм X, раніше обчислюваний в часі O (N), насправді обчислюється в o (n)"
Таким чином, кожен знає, що ваш алгоритм швидше - наскільки незрозуміло, але вони знають його швидше. Теоретично. :)