Я намагаюся зрозуміти, що саме Великий Опозначення. Я розумію це в буквальному і практичному сенсі, переглядаючи відповіді на подібні питання в ЗО. Але те, що відповіді не пояснюють, і я не розумію, це математична основа за нею. Формальне визначення стверджує, що
A function T(n) is the Big-O notation of f(n), if and only if there exist two constants c, n0 > 0 such that
T(n) <= c * f(n) for all n >= n0.
Я розумію інтуїтивно певною мірою, що цеРівняння намагається обчислити верхню межу в термінах деякої функції, яка має більш високий нахил у сенсі, щось у вищому кінці функції f (n). Я знаю, що моє розуміння нечітке. Так може хтось, будь ласка, пояснити математичну основу / уявлення Big-O нотації.
Відповіді:
2 для відповіді № 1Спочатку дозвольте мені просто сказати, що якщо g (n) є функцією н, потім O (g (n)) є набір всіх функцій f (n) такі, що існують такі константи c, N> 0, що f (n) <= cg (n) для всіх n> = N.
Якщо аналізувати алгоритм точно, тоді виникає функція вхідного розміру н, сказати f (n), що може бути складним дратівливим поліноміальним виразом у н (або складний вираз, що включає експонент).
Наприклад, можна виявити, що алгоритм, враховуючи вхідний розмір н, має точно f (n) = 2n ^ 2 + 3n + 1 інструкції. Але ми не дбаємо про 3n + 1 частина. Якщо н стає дуже великим, n ^ 2 ст ф буде домінувати в умовах нижчого порядку. Наприклад, для n = 100 ми це вже знаємо 2 * 100 ^ 2 є набагато більш значним, ніж 3 * 100 + 1.
Отже, щоб зробити цю ідею більш суворою, ми хотіли б сказати, щоf (n) зростає в гіршому випадку, як n ^ 2 ". У математичній нотації: f (n) - елемент O (n ^ 2). Тепер, як ви вже говорили у своєму питанні, донасправді довести, що f (n) є елементом O (n ^ 2), нам потрібно знайти константи c і N такі, що для всіх n> = N маємо f (n) <= cn ^ 2. Отже, якщо ми спробуємо c = 3, то отримаємо нерівність f (n) <= 3 * n ^ 2, і якщо ви будете грати алгебраїчно, то ви знайдете, що для всіх n> = 5 це справедливо. = 3 і наше N = 5. Дійсно, f (n) зростає в гіршому випадку, як n ^ 2.
Зверніть увагу на слова "у гіршому випадку". Було б неправильно говорити "f (n) росте як ..."замість цього ми говоримо "f (n) зростає в гіршому випадку, як ... ".
Щоб дати вам інший приклад, розглянемо наші f (n) = 2n ^ 2 + 3n + 1 знову. Моє твердження - це f (n) не є елементом O (n). Щоб насправді показати, що це правда, нам потрібнопоказують, що для всіх c, N> 0 існує n> = N такий, що f (n)> cn. Ну, f (n)> cn вірно, якщо і тільки якщо 2n ^ 2 + (3-c) n + 1> 0, що справедливо для досить великого n> = N (незалежно від того, що N є), Я дозволю вам розробити деталі. Це показує, що f (n) зростає гірше, ніж лінійна.
Ще один приклад з нашим f (n) = 2n ^ 2 + 3n + 1: Можна показати, що f (n) є елементомO (n ^ 3). Потрібно знайти c, N> 0 таке, що f (n) <= cn ^ 3 для всіх n> = N. Ну, спробуйте c = 1, після чого можна знайти деяку алгебру що це справедливо для N = 4. Це гарантує, що "f (n) зростає в найгіршому випадку, як ..." настрої, якщо ви можете показати, що ваша функція f знаходиться в деякому великому-O, то там може бути "краще великий O ”, для якої він є частиною.
Як остаточну вправу, показано, що O (1) є a правильний підмножина O (n), яка є a правильний підмножина O (n ^ 2), що є a правильний підмножина O (n ^ 3), що є a правильний підмножина O (n ^ 4), ...
1 для відповіді № 2
g (n) = O (f (n)) означає, що після певного n (для n> n0) g (n) / f (n) <= M (фіксована величина) Наприклад, g (n) = n є O (n) і O (n * log (n)) як для n0 = 2:
n / n = 1 <= 1 = M
n / (n * log (n)) <= 1 / log (2) = M