我正在学习大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)指的是一个函数(或算法,或算法中的步骤),其工作时间与输入大小的对数成正比(大多数情况下通常以2为基数,但并不总是以2为底,在任何情况下,通过big-O符号*,这都是无关紧要的)。
对数函数是指数函数的倒数。换句话说,如果您的输入呈指数增长(而不是通常认为的线性增长),则函数呈线性增长。
O(logn)运行时间在任何一种分而治之的应用程序中都很常见,因为(理想情况下)每次都会将工作减半。如果在每一个除法或征服步骤中,你都在做恒定时间的工作(或不是恒定时间的,但随着时间的增长比O(log n)慢),那么你的整个函数就是O(log)。相当常见的是,每个步骤都需要输入线性时间;这将相当于O(n log n)的总时间复杂度。
二进制搜索的运行时间复杂性是O(logn)的一个例子。这是因为在二进制搜索中,通过将数组分成两半,并且每一步只关注一半,您总是忽略后面每一步的一半输入。每一步都是恒定的时间,因为在二进制搜索中,您只需要将一个元素与关键字进行比较,就可以确定下一步要做什么,而不管您考虑的数组在任何时候都有多大。因此,大约执行log(n)/log(2)步。
合并排序的运行时间复杂性是O(n log n)的一个例子。这是因为每一步都将阵列一分为二,总共约为log(n)/log(2)步。然而,在每一步中,您都需要对所有元素执行合并操作(无论是对n/2个元素的两个子列表执行一次合并操作,还是对n/4个元素的四个子列表执行两次合并操作都是无关紧要的,因为这增加了每一步对n个元素执行合并的必要性)。因此,总复杂度为O(n log n)。
*记住,根据定义,big-O表示法并不重要。同样,通过改变对数的基数规则,不同基数的对数之间的唯一差异是一个常数因子。
这个问题已经有了很多好的答案,但我相信我们真的错过了一个重要的答案,那就是图解的答案。
说一个完整的二叉树的高度是O(logn)是什么意思?
下图描述了一个二叉树。请注意,与上面的级别相比,每个级别包含的节点数量是两倍(因此是二进制的):
二进制搜索是一个复杂度为O(logn)的示例。假设图1中树底部的节点表示某个排序集合中的项目。二进制搜索是一种分而治之的算法,图中显示了我们需要(最多)4次比较才能找到我们在这个16项数据集中搜索的记录。
假设我们有一个包含32个元素的数据集。继续上面的图,发现我们现在需要5次比较才能找到我们正在搜索的内容,因为当我们乘以数据量时,树只增长了一层。结果,该算法的复杂性可以用对数级数来描述。
在一张普通纸上绘制对数(n)将生成曲线图,其中曲线的上升速度随着n的增加而减慢: