为了账号安全,请及时绑定邮箱和手机立即绑定

O(log2n)是数学公式吗?

/ 猿问

O(log2n)是数学公式吗?

FFIVE 2018-10-11 21:19:05

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

查看完整描述

3 回答

?
qq_慕村6119366
不是 是高中的知识
查看完整回答
反对 回复 2019-07-10
?
qq_笑_17

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

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


查看完整回答
反对 回复 2018-10-21
?
扬帆大鱼

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

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


查看完整回答
反对 回复 2018-10-21
  • 3 回答
  • 0 关注
  • 1008 浏览
我要回答

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信