访问单向链表和顺序数组第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)。其他操作时间代价见下表: 数据结构与算法 2024-06-17 31 点赞 0 评论 46 浏览