链表的平均搜索时间不应该是O(N/2)吗？

Question

我一直看到链接列表的搜索时间列为O(N),但是如果列表中有100个元素,那么在找到匹配项之前,您平均只与50个元素进行比较吗？

那么O(N/2)是否被舍入为O(N),或者我认为链接列表查找的平均N/2是错误的吗？

谢谢!

Answer 1

问题是,顺序实际上只是谈论时间随着n的增加而增加.

所以O(N)意味着你有线性增长.如果你翻倍,N那么所用的时间也会增加一倍.N/2并且N两者都具有相同的增长行为,因此就订单而言,它们是相同的.

像log(N),和N^2另一方面具有非线性增长的功能,N^2例如意味着如果你加倍N的时间增加4倍.

这完全取决于比率.如果1件物品平均需要1分钟,2件物品平均需要2分钟或4分钟吗？O(N)将是2分钟,O(N ^ 2)将需要4分钟.如果原始时间为1秒,则O(N)将花费2秒,O(N ^ 2)为4秒.

花费1分钟的算法和花费1秒的算法都是O(N)!