c - O(log2n)是数学公式吗？

问题描述

问 题

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

解决方案

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

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

这篇关于c - O(log2n)是数学公式吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！