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

O(Log N)到底是什么意思?

/ 猿问

O(Log N)到底是什么意思?

O(Log N)到底是什么意思?

我目前正在学习大O符号运行时间和摊销时间。我理解O(N)线性时间,这意味着输入的大小成比例地影响算法的增长.同样的情况也是如此,例如,二次时间O(N)2)等.甚至算法,如置换生成器,与O(n!)时间的增长是因式分解的。

例如,以下函数是O(N)因为该算法与其输入量成比例增长。n:

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

类似地,如果存在嵌套循环,则时间为O(N)2).

但究竟什么是O(原木n)?例如,说一个完整二叉树的高度是什么意思?O(原木n)?

我确实知道(也许不是很详细)什么是对数,从这个意义上说:日志。10100=2,但我不知道如何识别具有对数时间的函数。


查看完整描述

3 回答

?
九州编程

许多好的答案已经张贴在这个问题上,但我相信我们确实遗漏了一个重要的答案-即有插图的答案。

说一个完整二叉树的高度是O(Logn)是什么意思?

下图描绘了一棵二叉树。请注意,与上述级别相比,每个级别包含的节点数是其数量的两倍(因此,双星):


二进制搜索是一个复杂的例子。O(log n)..假设图1中树底部的节点表示某些排序集合中的项。二进制搜索是一种分而治之的算法,图中显示了我们需要(最多)4次比较才能在这16项数据集中找到我们正在搜索的记录。

假设我们有一个包含32个元素的数据集。继续上面的绘图,以发现我们现在需要5个比较才能找到我们正在寻找的东西,因为当我们乘以数据量时,树只增长了一个层次。因此,算法的复杂度可以描述为对数阶。

绘图log(n)在一张普通的纸上,会产生一个曲线上升减速的图形。n增加:


查看完整回答
反对 2019-06-18
?
噜噜哒

O(log N)基本上意味着时间线性上升,而n指数上升。所以如果需要1第二次计算10元素,它将需要2计算秒100元素,3计算秒1000元素等等。

O(log n)当我们进行分而治之的算法时,例如二进制搜索。另一个例子是快速排序,每次我们将数组分成两个部分,每次O(N)是时候找一个枢轴元素了。因此它N O(log N)


查看完整回答
反对 2019-06-18
  • 3 回答
  • 0 关注
  • 1737 浏览

添加回答

回复

举报

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