风中咖啡豆

文章
5
资源
0
加入时间
2年10月21天

访问单向链表和顺序数组第i个元素的时间复杂度的分析

假设链表L有n个元素,如果这n个元素中每一个元素被访问的概率都为相同,则访问到第i个元素所前移的指针的平均次数为:Average = (1+2+3+......+n)/n = n(1+n)/2/n = n/2 + 1/2所以,访问第i个元素的平均时间为O(n)。相比起来,在数组L中访问第i个元素的平均时间为O(1)。其他操作时间代价见下表: