O(log2n)是数学公式吗？

Question

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

Answer 1

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

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

Answer 2

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

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

Answer 3

是高等数学里面的符号，这类符号叫做渐进符号，用来描述一个函数的数量级。

算法里面常用的有这些：
大O表示渐进上界，比如O(logn)就表示函数数量级的上界不会超过log(n)。
Θ表示渐进确界，相当于同一数量级。
Ω表示渐进下界。

需要注意的是，由于历史原因，大O常被误用为渐进确界，不过已经约定俗成了。

这些不光算法分析里面会用到，分析无穷级数的时候也会经常要用到。

PS：关于大O与Θ的历史纠葛，可以参考算法导论的函数增长那一章最后的注记。

Answer 4

我感觉没上过大学的话 急需补充的不是数学课 而是英语 然后你就可以去google了 基本上你想知道的数学问题都能搜到靠谱的解释（某度的结果你懂的） 学一年英语你就能这样了 学一年数学我感觉意思不大