O(log2n)是数学公式吗？

Question

再看算法的时候看到二分法的公式是这个，想问下，O(log2n)是否是高等数学中的公式？因为我是初中毕业，没学过高等数学，求解，如果是，他的含义又是什么？

Answer 1

不是 是高中的知识

Answer 2

大O计法，用来表示复杂度的，O(log2n)在这里是指时间复杂度，不过一般是这么记的O(logN)，会省略掉那个底数2。

比如一个有序的序列，使用二分法在其内部查找一个元素，那么如果这个序列的元素个数是N的话，理论上查找次数的上限就是logN，所以就说二分查找的时间复杂度是O(logN)。

Answer 3

这是复杂度的一种表达方法。

大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))