Как я могу доказать, что 1 / n - это O (1)?

Question

Как я могу математически доказать, что 1 / n есть O (1)?Я не понимаю, с чего начать.Любая помощь?

Answer 1

Как говорит проблема, начните с определения нотации big-O.

F(x) = O(G(x)) IFF there exist constants k and m, 
such that for all n > m, k*|G(n)| > F(n). 

(Проконсультируйтесь с вашим textboox для точной формулировки здесь.)

Неофициально, это означает, что если мы пойдем достаточно далеко, в конечном итоге G (n) будет доминировать над F (n), независимо от того, насколько велико начальное преимущество, которое мы даем F (n) через постоянные факторы.

---

Итак, как вы можете доказать что-то подобное?

Доказательства, подобные этому, как правило, делаются конструктивно - показывают, что конкретные правильно выбранные значения для m и k приводят к неравенству.

Теперь вы просто занимаетесь алгеброй. Найдите некоторые m и k, которые удовлетворяют формальному определению. В зависимости от требуемого уровня формальности / детализации вам может потребоваться доказать, что 1 / n монотонно уменьшается (или сделать некоторое доказательство индукции), чтобы показать, что ваш выбор m и k действительно работает.

---

Маргус (и Loadmaster): асимптотическая нотация говорит о функциях и полностью независима от базового оборудования и реализации. 1 / n = O (1) - математическая истина, которая не основывается даже на существовании вещей, которые мы называем «компьютерами». Если вы думаете о количестве инструкций, вы рассуждаете о классах сложности (например, P, NP, EXP), а не об асимптотических обозначениях.

Answer 2

Хорошо, давайте подумаем об этом на минуту. У нас есть две функции f (n) = 1 / n и g (n) = 1. Нам нужны две константы C и k, такие что 0 <= f (n) <= C * g (n) всякий раз, когда n> k. Если область обеих функций ограничена набором всех натуральных чисел, мы просто выбираем C = 2 и k = 0. Тогда мы имеем 0 <= 1 / n <= 2 * 1 для всех n> 0. Здесь мы называем C, а k свидетелями отношения 1 / n является O (1).

Нужно доказать это немного более строго? Ну ... ясно 1 / n <1 <strong>тогда и только тогда, когда 1 1, а если n> 1, мы знаем, что это означает 1 / n <1, и в этом случае 2 * 1> 1 / n.

Answer 3

Если вы демонстрируете это для алгоритма, начните с указания, что на входе будет положительное количество данных (N> = 1), вы не можете ввести 1/2 данных:)

После этого,продемонстрируйте, что 1 / n является растущей функцией, когда n> 1, вы должны использовать индукцию для этого, и вы готовы идти вперед, потому что вы уже указали, что n будет больше 1 всегда!

Answer 4

Вам на самом деле не нужно доказывать это, это факт.верхняя граница 1 / n с учетом того, что n является натуральным числом больше 0, всегда равна 1.