Я хочу, чтобы узнать, как подойти следующий вопрос:Экспоненциальная запись BIG O?
Какие из следующих функций на единицу больше, порядок роста?
(1/3)^nили17?
Я попытался найти ответ, но мне не удалось найти четкое и простое объяснение того, как рассчитать это.
Эта проблема не похожа на большинство примеров, потому что ни одна из функций не растет в смысле «возрастания, поскольку увеличивается n».
Во-первых, f(n) = 17 является постоянным. Независимо от того, что n есть f(n) не 17.
Теперь g(n) = (1/3)^n фактически уменьшается как n увеличивается (1/3, 1/9, 1/27, ..., с пределом, равным нулю, как n идет к бесконечность). Поэтому из определения большого О, это легко найти константы c и n0 таким образом, что
c*(1/3)^(n) <= 17, n >= n0
Одним из вариантов является просто c = n0 = 1, так g = O(f).
Жаль, что я написал это ошибочно – Iony
Это было моя ошибка, во время моего редактирования вопроса я как-то случайно изменил '(1/3) n' на' (1/3)^n', что, очевидно, очень отличается –
@KevinWells А, ну, тогда это легко. (1/3) n растет, 17 нет. Они оба O (n), но в то время как 17 = O (1), но 1/3n нет. – chepner
Любой анализ книги алгоритмов будет охватывать это. Кроме того, см. [Здесь] (https://mitpress.mit.edu/sicp/full-text/sicp/book/node17.html). –
Возможный дубликат [Простое английское объяснение Big O] (http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) –
@KevinWells, если честно, он спрашивает, как найти/рассчитать порядок, а не то, что он есть. Я бы сказал, что это лучший кандидат на двуличие: http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it. Хотя вопрос, похоже, подразумевает, что он этого не понимает. – goodguy5