Вы задали несколько вопросов здесь. Давайте обратимся к каждому из них по очереди:
В книге, кажется, говорится, пока я могу найти константу C и некоторое число n> нет, где f (x) <= C* g (х), тогда я могу сделать вывод, что f (x) = O (g (x)). Казалось бы, индуктивные рассуждения потребуются, чтобы доказать, что они верны для всех n, о которых в книге ничего не говорится! </p>
Это действительно формальное определение обозначения big-O. Однако ничто в этом определении не требует использования индукции. Например, предположим, что я хочу доказать, что 2n + 137 = O (n). Я выберу c = 3 и n 0 и покажу, что эти константы имеют свойства, которые мы хотим. В частности, выберите любое n ≥ 137. Тогда
2n + 137
≤ 2n + n (так как 137 ≤ n)
= 3n,
и мы приехали сюда без всякой индукции.
Я также вижу, как некоторые люди отвечают на вопросы, используя определение большого О (хотя для небольшого О), но я не видя в книге. А именно O:
f (x) = O (g (x)), если существует lim n-> ∞ f (x) / g (x)
Считается ли это более строгим доказательство определения асимптоти c границ?
Это интересно. Представьте, что f и g - это функции, где существует lim n → ∞ (f (n) / g (n)). Тогда действительно у вас будет f (n) = O (g (n)). Одним из способов увидеть это является использование формального определения пределов на бесконечности. В частности, если L конечно, то по определению
lim n → ∞ h (n) = L тогда и только тогда, когда для любого ε> 0 существует n ε такой, что | h (n) - L | ≤ ε для всех n ≥ n ε .
Итак, предположим, что lim n → ∞ = L для некоторой константы L. Теперь выберите ε = 1 , так что есть некоторые n 1 , где для любого n ≥ n 1 имеем
| f (n) / g (n) - L | ≤ 1.
В частности, это означает, что
f (n) / g (n) - L ≤ 1,
Итак
f (n) ≤ (1 + L) г (n)
Сбор c = 1 + L и n 0 = n 1 , то дает нам константы, которые нам нужны, чтобы доказать f (n) = O (g (n)).
Иными словами, если этот предел существует, то f (n) = O (g (n)).
Однако, возможно, что f (n) = O (g (n)), даже если этот предел не существует. Например, выберите f (n) = 2 + sin n и g (n) = 1. Тогда f (n) = O (g (n)), но тогда предел f (n) / g (n) не равен не существует, потому что значения колеблются к бесконечности. Так что обратное утверждение неверно.
Я думаю - но я не уверен на 100% - что если вы замените предел на более высокий предел, вы получите эквивалентность, но мне нужно подумать об этом больше. о.
Является ли это более «строгим» способом делать доказательства большого размера? Я бы так не сказал. Это так же строго, как сделать это другим способом, хотя это может быть более полезно, если вы пытаетесь построить интуицию.
Если это так, я понимаю, что Ω:
f (x) = Ω (g (n)), если lim n-> ∞ f (x) / g (x)> 0
и Θ равно: f (x) = Ω (g (n)) Λ f (x) = Ω (g (n))
Очень близко! Как упоминалось выше, предельная уловка не является «определением» нотации big-O, поскольку она не обрабатывает все случаи, поэтому вы не можете определить нотацию Ω таким образом. Тем не менее, ваше определение Θ нотации точечно.
Надеюсь, это поможет, и удачи!