"算法A的最坏情况运行时间"和"算法A的运行时间为O(n)"这两个陈述有区别吗?
我认为它们没有区别,因为最坏情况是函数可能需要的最长运行时间,O(n)表示函数被"限制在"某个范围内。两者的意思相同。
希望我的逻辑是正确的。
"算法A的最坏情况运行时间"和"算法A的运行时间为O(n)"这两个陈述有区别吗?
我认为它们没有区别,因为最坏情况是函数可能需要的最长运行时间,O(n)表示函数被"限制在"某个范围内。两者的意思相同。
希望我的逻辑是正确的。
有所差异。
算法的时间复杂度O(f)并不准确:你必须在最好/最坏/平均情况下说明算法的时间复杂度是O(f)。当最好、最坏和平均情况相同时,可以说它是O(f),但这种情况并不常见。
我同意你的观点,但是有些常见算法(例如快速排序)的期望时间比最坏情况要好得多。你可以说快速排序的最坏情况是O(N^2),但你仍然期望它几乎总是O(N*log N)(至少对于一个好的实现)。
对于具有分摊行为的算法,情况会变得更加复杂。你可能会得到一个特定操作的O(N)或O(log N),但是连续进行多个操作时,在分摊意义下始终是O(1)。Splay树和Finger树是这一类的好例子。
在编程中,运行时间作为绝对度量通常比当你添加更多数据时该时间如何增加不那么重要。例如,一个算法始终需要5秒来处理100个项目,需要10秒来处理200个项目等等,被称为O(N),因为运行时间随着数据集大小的线性增长而增加。如果第二个算法花费了5*5=25秒来处理这200个项目,它可能被归类为O(N^2)。这里没有“峰值运行时间”,因为当你向其添加更多数据时,运行时间总是增加。
事实上,大O表示上限-因此,您可以说第一个算法也是O(N^2)(如果N是上限,则N*N更高,因此也是上限,尽管是松散的)。用于表示其他上限的常见符号包括Ω(omega,下限)和Θ(theta,同时下限和上限)。
一些算法(例如快速排序)根据输入的数据表现出不同的行为-因此,最坏情况是O(N^2),即使它通常表现得像O(N log N)。
这些单词串之间存在巨大的差异。"算法A的最坏情况运行时间"是一个名词从句,它根本没有陈述任何内容。"算法A的运行时间为O(n)"是一个句子,告诉我们有关A的一些信息。
ArrayList
(Python中的list
,Ruby中的Array
等类似)提供了分摊的O(1)附加操作,但如果你恰好是触发调整大小的幸运附加操作,你将得到比平均情况慢得多的响应。 - Hank Gay