再看算法的時候看到二分法的公式是這個，想問下，O(log2n)是否是高等數學中的公式？因為我是初中畢業，沒學過高等數學，求解，如果是，他的含義又是什么？
3 回答
qq_笑_17
TA貢獻1818條經驗 獲得超7個贊
大O計法，用來表示復雜度的，O(log2n)在這里是指時間復雜度，不過一般是這么記的O(logN)，會省略掉那個底數2。
比如一個有序的序列，使用二分法在其內部查找一個元素，那么如果這個序列的元素個數是N的話，理論上查找次數的上限就是logN，所以就說二分查找的時間復雜度是O(logN)。
揚帆大魚
TA貢獻1799條經驗 獲得超9個贊
這是復雜度的一種表達方法。
大O符號表示漸進上線，用比較數學的語言來表達就是，存在一個正整數x，當n>=x時，f(n) <= g(n)，那么f(n) = O(g(n))，針對你的case，g(n) = log2(n)
說到這里，不提一些平級概念就有點太不厚道了：
Ω符號表示表示漸進下線，用比較數學的語言來表達就是，存在一個正整數x，當n>=x時，f(n) >= g(n)，那么f(n) = O(g(n))；
f(n) = θ(g(n))，當且僅當f(n) = O(g(n))且f(n) = Ω(g(n))
如果f(n) = O(g(n))且f(n) ≠ θ(g(n))，則f(n) = o(g(n))
- 3 回答
- 0 關注
- 3595 瀏覽
添加回答
舉報
0/150
提交
取消