Sof*_*Guy 3 algorithm big-o runtime
我在一本书中读到,下面的表达式O(2^n + n^100)将被简化为:O(2^n)当我们删除无关紧要的部分时.我很困惑,因为根据我的理解,如果值n是3那么部分n^100似乎有更高的执行次数.我错过了什么？
Big O表示法本质上是渐近的,这意味着我们认为表达式为n趋于无穷大.
你是正确的,对于n = 3,n^100大于2^n但一旦N> 1000,2^n是不是总是更大n^100,所以我们可以忽略n^100在O(2^n + n^100)对于n远远大于1000.
对于Big O表示法的正式数学描述,维基百科文章做得很好
对于较少的数学描述,这个答案也做得很好: