-1
Я могу это доказать, но я понятия не понимаю, почему 3^n находится в O (10^n). Я ошибаюсь?Big-Oh: Является ли f (n) = 3^n в O (g (n)) = 10^n?
A
ответ
0
Концептуально, чем больше основание экспонента, тем быстрее рост функции.
Big-O дает нам верхнюю границу; то есть заданы две функции f(n) и g(n), если для всех значений n выше определенного порогового значения (за исключением некоторых мелких деталей, таких как константное кратное), g(n) доминирует над f(n), то можно сказать, что f(n) = O(g(n)).
Теперь, для любого n >= 0, должно быть ясно, что 10^n по крайней мере невелик (но большую часть времени намного больше), чем 3^n.
Обратите внимание, что это не особенно полезно сказать, что 3^n = O(10^n). Это не связано с какими-либо средствами; темпы роста этих двух функций резко различаются. Более эффективная граница для 3^n сама по себе —, то есть 3^n = O(3^n).
+0
Да, это именно то, что я понял, потому что граница не является «жесткой», I запутался, если он вообще считался o (g (n))! Я просто хотел подтвердить, что все равно будет правильным, даже если это не полезно. – TimelordViktorious
+0
Да, это действительно правильно, но не полезно. Мы могли бы также сказать, что «1 = O (10^n)». Хотя это верно, это действительно не полезно; функция порядка 1 имеет постоянную рабочую среду, а функция порядка '10^n' имеет экспоненциально худшее время исполнения. – Purag
+1
@ MH1993 Обратите внимание, что вы должны быть осторожны при написании с помощью 'o' (little-oh) vs' O' (big-oh). Они означают две разные вещи: 'o' означает, что определенная граница не является жесткой,' O' означает, что она может быть или не быть. '' '' '' '' '' '' '<='. – Paulpro
Смежные вопросы
- 1. функции f (n) не являются O (g (n)), а g (n) не является O (f (n))
- 2. Докажите max (O (f (n)), O (g (n))) = O (max (f (n), g (n))
- 3. В асимптотическом анализе покажите, что: - O (f (n) + g (n)) = O (max {f (n), g (n)})
- 4. , если f (n) = o (g (n)), то g (n) + f (n) = Θ (g (n))?
- 5. Отображение f (n) = O (f (n) + g (n))?
- 6. Если f (n) = O (g (n)), то log (f (n)) = O (log (g (n))?
- 7. f (n)/log (n) = O (g (n)) ⇒ g (n) = Θ (f (n))?
- 8. Доказательство n^2 - 10n не является O (n) от противного.
- 9. Докажите, что f (n) = o (g (n)) влечет за собой 2^f (n) = o (2^g (n))
- 10. Может ли f (n) принадлежать как o (g (n)), так и большому омегу (g (n))?
- 11. Может ли 3n³ + 4n-5 == O (n²)?
- 12. Что такое обозначение заказа f (n) = O (g (n))?
- 13. Может ли кто-нибудь объяснить, почему f (n) + o (f (n)) = theta (f (n))?
- 14. Является ли O (n^n) и O (n!) Эквивалентным?
- 15. Является ли O (n) + O (n log n) равным O (n log n)?
- 16. , если f (n) = n-100 и g (n) = n-200 равно f, равному большому o из g или омега g или тета g
- 17. O (log 10n) или O (log n) x 10 быстрее?
- 18. Асимптотика. Если f (n) = theta (g (n)) и g (n) = theta (h (n)), то почему h (n) = theta (f (n))
- 19. Доказательство f (n) равно O (2^n)
- 20. Если f (n) = O (h (n)), то c * f (n) = O (h (n)) для всех c> 0 - доказательство оспаривается?
- 21. Является ли O (log n) всегда быстрее, чем O (n)
- 22. Является ли сложность O (log (n)) эквивалентной O (sqrt (n))?
- 23. Большая сложность O, когда две функции f (n) [O (1)] и g (n) [O (n)] умножаются вместе
- 24. Какая пара функций удовлетворяет f (N) ~ g (N)?
- 25. Стэнфордская викторина Асимптотический анализ? Предположим еще два (положительные неубывающие функции f и g такие, что f (n) = O (g (n)). Является ли 2^f (n) = O (2^g (n))?)
- 26. Big O of f (n) = N! + 2^N
- 27. Что означает O (O (f (n)))?
- 28. Что такое математическое определение f (n) и O (f (n))
- 29. Является большим o для следующего O (n^2 * log (n)) или O (n^3 * log (n))
- 30. Может ли O (N * N) быть быстрее, чем O (N)
'3^n' находится в' O (10^n) ', потому что он не растет асимптотически быстрее, чем' 10^n'. Конечно, это не слишком сложно. '3^n' также находится в' O (3^n) ', что является плотной границей. – Paulpro
'h (n) = 1' и' i (n) = n' также оба находятся в 'O (10^n)' – Paulpro