对n ^ 2 vs 2 ^ n的大O感到困惑
这个问题在这里已经有了答案：
大O符号本质上是渐近的，这意味着我们认为表达式n趋于无穷大。
你是对的，对于n = 3， n^100大于2^n但是一旦n> 1000，2 2^n总是大于n^100所以我们可以忽略n^100在O(2^n + n^100)比n大得多。
对于大O符号的正式数学描述，维基百科文章做得很好
对于一个不那么数学的描述，这个答案也做得很好：
“大O”符号的简单英文解释是什么？
你错过了O(n)是渐近复杂性的事实。 更严格地讲，当n -> infinity时，你可以计算lim(2^n / n^100) ，你会看到它等于无穷大，所以它意味着渐近地2^n增长得比n^100快。
当用n来度量复杂度时，应该考虑n的所有可能值，而不仅仅是一个例子。 所以在大多数情况下，n大于100.这就是n ^ 100不重要的原因。
链接地址: http://www.djcxy.com/p/6757.html