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

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 回答

?
蛊毒传说

我无法理解如何用日志时间来标识函数。

对数运行时间函数最常见的属性是:

  • 选择执行某些操作的下一个元素是几种可能性之一,
  • 只需要选择一个。

  • 执行操作的元素是n的数字。

这就是为什么,例如,在电话簿中查找人是O(Logn)的原因。你不需要检查每一,每个在电话簿上找一个合适的人;相反,你可以通过按字母顺序查找他们的名字来分而治之,而在每个章节中,你只需要在最终找到某人的电话号码之前,探索每个部分的一个子集。

当然,一本更大的电话簿仍然要花更长的时间,但它不会像增加的尺寸的比例增长那么快。


我们可以扩展电话簿示例,以比较其他类型的操作和他(她,它)们的跑步时间。我们假设我们的电话簿企业(“黄页”)具有独特的名称和人民(“白页”),它可能没有唯一的名称。一个电话号码最多分配给一个人或企业。我们还将假定切换到特定页面需要一定的时间。

下面是我们可能在电话簿上执行的一些操作的运行时间,从最好到最坏:

  • O(1)(最佳情况):给定企业名称和业务名称的页面,请查找电话号码。

  • O(1)(平均情况):给定一个人的名字和他们的名字的页面,找到电话号码。

  • o(原木n):给出一个人的名字,找出电话号码,在你还没有搜索的书的一半左右随机选择一个点,然后检查这个人的名字是否在那个位置。然后,在书的一半部分重复这个过程,这个部分是人的名字所在。(这是对个人姓名的二进制搜索。)

  • o(N):查找所有电话号码包含数字“5”的人。

  • o(N):给出一个电话号码,找出该号码的人或企业。

  • O(n日志n):打印机的办公室出现了混乱,我们的电话簿上的所有页面都是随机排列的。通过查看每一页上的名称,然后将该页面放置在新的空电话簿中的适当位置,从而修复订单,使其正确。

下面的例子,我们现在打印机的办公室。电话簿正在等待邮寄给每个居民或企业,每本电话簿上都有一张标签,标明应该邮寄到哪里。每个人或企业都有一本电话簿。

  • O(n日志n):我们想要个性化的电话簿,所以我们将在他们指定的副本中找到每个人或企业的名字,然后在书中圈出他们的名字,并为他们的赞助写一封简短的感谢信。

  • O(N)2):办公室发生了一个错误,每本电话簿的每一个条目在电话号码的末尾都有一个额外的“0”。取一些白色的,去掉每一个零。

  • O(n·n!):我们准备好把电话本装上船坞了。不幸的是,那个本应装书的机器人已经不知所措了:它正在随机地把书放到卡车上!更糟糕的是,它把所有的书都装到卡车上,然后检查它们的顺序是否正确,如果没有,它会卸载它们,然后重新开始。(这是令人恐惧的Bogo排序.)

  • O(N)n):你修理机器人,这样它就能正确地装载东西。第二天,你的一个同事拿你开玩笑,把装货码头的机器人连到自动打印系统上。每当机器人去加载一本原著时,工厂的打印机就会复制所有的电话簿!幸运的是,机器人的bug检测系统已经足够复杂了,当它遇到一本复制的书来加载时,它不会尝试打印更多的副本,但是它仍然需要加载每一本已经打印出来的原始和复制的书。

要获得更多的数学解释,您可以查看时间复杂性是如何到达的。log n这里。https:/hackernoon.com/什么-时间复杂度-o-log-n-实际上-平均-45f94bb5bfbf


查看完整回答
反对 回复 2019-06-18
?
九州编程

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

说一个完整二叉树的高度是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 关注
  • 959 浏览
我要回答
慕课专栏
更多

添加回答

回复

举报

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