为什么单链表的访问时间复杂度不是n-1而是n？

• 你提到的操作逻辑是完全成立的：单链表的每个节点都通过next指针存储后继节点的地址，确实只需要从首节点出发执行n-1次指针跳转，就能访问到第n个节点的内容，无需完成第n次跳转。
• 但你对时间复杂度的计数规则存在误解：我们日常使用的大O时间复杂度，描述的是算法开销随数据规模增长的渐进趋势，计算时会直接忽略所有常数项和低阶项。n-1和n的增长趋势完全一致，所以统一会被记作O(n)，行业内没有单独使用O(n-1)来描述单链表遍历复杂度的惯例。

可以用极端场景验证这个逻辑：如果n=1，你不需要做任何指针跳转就能拿到首节点值，对应操作次数是0 = 1-1，但这种个位数的常数差异，在n的规模达到成千上万甚至更大的时候，对整体效率的影响可以完全忽略，不会改变复杂度的量级。

内容的提问来源于stack exchange，提问作者Muhammad Rameez