我正在学习大O符号的运行时间和摊销时间。我理解O(n)线性时间的概念,这意味着输入的大小成比例地影响算法的增长。。。例如,二次时间O(n2)等也是如此。甚至是通过阶乘增长的算法,如置换生成器,其O(n!)次。
例如,以下函数为O(n),因为算法与其输入n成比例增长:
f(int n) {
int i;
for (i = 0; i < n; ++i)
printf("%d", i);
}
类似地,如果存在嵌套循环,时间将为O(n2)。
但O(log n)到底是什么?例如,说一个完整的二叉树的高度是O(log n)是什么意思?
我确实知道(也许不是很详细)对数是什么,从这个意义上说:log10 100=2,但我不知道如何识别具有对数时间的函数。
这个问题已经有了很多好的答案,但我相信我们真的错过了一个重要的答案,那就是图解的答案。
说一个完整的二叉树的高度是O(logn)是什么意思?
下图描述了一个二叉树。请注意,与上面的级别相比,每个级别包含的节点数量是两倍(因此是二进制的):
二进制搜索是一个复杂度为O(logn)的示例。假设图1中树底部的节点表示某个排序集合中的项目。二进制搜索是一种分而治之的算法,图中显示了我们需要(最多)4次比较才能找到我们在这个16项数据集中搜索的记录。
假设我们有一个包含32个元素的数据集。继续上面的图,发现我们现在需要5次比较才能找到我们正在搜索的内容,因为当我们乘以数据量时,树只增长了一层。结果,该算法的复杂性可以用对数级数来描述。
在一张普通纸上绘制对数(n)将生成曲线图,其中曲线的上升速度随着n的增加而减慢:
我无法理解如何使用日志时间标识函数。
对数运行时间函数最常见的属性是:
选择下一个要执行某些操作的元素是多种可能性之一,并且只需要选择一个。
or
执行操作的元素是n的数字
这就是为什么,例如,在电话簿中查找人是O(logn)。你不需要检查电话簿上的每个人,就能找到合适的人;相反,你可以简单地根据他们的名字的字母顺序进行划分和征服,在每个部分中,你只需要探索每个部分的一个子集,就可以最终找到某人的电话号码。
当然,一本更大的电话簿仍然需要更长的时间,但它的增长速度不会像增加电话簿的比例那样快。
我们可以扩展电话簿示例,以比较其他类型的操作及其运行时间。我们将假设我们的电话簿中有具有唯一名称的业务(“黄页”)和可能没有唯一名称的人员(“白页”)。电话号码最多分配给一个人或一家公司。我们还将假设翻到特定页面需要恒定的时间。
以下是我们可能在电话簿上执行的一些操作的运行时间,从最快到最慢:
O(1)(在最坏的情况下):给定企业名称所在的页面和企业名称,找到电话号码。O(1)(在一般情况下):给定一个人的名字和他们的名字所在的页面,找到电话号码。O(log n):给定一个人的名字,在书中你还没有搜索到的部分的中途随机抽取一个点,然后检查这个人的名字是否在这个点上,从而找到电话号码。然后在书中人名所在的部分重复这个过程。(这是对人名的二进制搜索。)O(n):查找电话号码包含数字“5”的所有人。O(n):给定一个电话号码,找到拥有该号码的人或企业。O(n log n):打印机的办公室出现了混乱,我们的电话簿上的所有页面都以随机顺序插入。通过查看每一页上的名字,然后将该页放在新的空电话簿中的适当位置,修正顺序,使其正确。
对于以下示例,我们现在在打印机的办公室。电话簿等待邮寄给每位居民或企业,每个电话簿上都有一个标签,标明应该邮寄到哪里。每个人或企业都有一本电话簿。
O(n log n):我们想让电话簿个性化,所以我们将在他们指定的副本中找到每个人或企业的名字,然后在电话簿中圈出他们的名字,并为他们的惠顾写一封简短的感谢信。O(n2):办公室发生了一个错误,每个电话簿中的每个条目在电话号码末尾都有一个额外的“0”。取出一些白色,去掉每个零。O(n·n!):我们准备好把电话簿装到码头上了。不幸的是,原本要装书的机器人已经失控了:它正在把书按随机顺序放在卡车上!更糟糕的是,它把所有的书都装到卡车上,然后检查它们的顺序是否正确,如果不正确,它就把它们卸下来,重新开始。(这是可怕的bogo类型。)O(nn):你把机器人修好,这样它就能正确地装载东西。第二天,你的一个同事对你开了个玩笑,把装卸台机器人连接到自动打印系统上。每次机器人去装载一本原版书时,工厂打印机都会对所有的电话簿进行重复打印!幸运的是,机器人的错误检测系统足够复杂,当它遇到要加载的复制书时,它不会尝试打印更多的副本,但它仍然必须加载已打印的每一本原始和复制书。