Great question—this is such a common mix-up when getting to grips with array time complexities, so let’s break it down clearly!

为什么按索引取值是O(1)？ #

数组在底层是连续的内存块存储的。当你创建一个数组时，系统会给它分配一个起始内存地址（我们称之为“基地址”）。

要访问索引i对应的元素，电脑根本不需要逐个搜索——它只需要用一个简单公式就能算出该元素的精确内存位置：
基地址 + (i * 单个元素的字节大小)

这个计算过程是固定时间完成的，不管数组有多大。哪怕你的数组有10个元素还是1000万个元素，找到内存地址并取出值的工作量完全一样。这就是为什么这个操作的时间复杂度是O(1)（常数时间）。

那按值查找为什么是O(n)？ #

你说的完全没错！当你要找某个特定值（而不是用索引定位）时，电脑没办法直接跳到这个值的位置——除非数组是有序的，你能用二分查找这类更快的算法（时间复杂度为O(log n)）。

对于无序数组，唯一的办法就是逐个检查元素：从索引0开始，然后是1、2……直到找到目标值或者遍历完整个数组。最坏情况就像你举的例子——目标值在最后一位，或者根本不存在——这时候你得检查数组里的每一个元素。因为检查次数和数组长度n直接成正比，所以这个操作的时间复杂度是O(n)（线性时间）。

快速总结避免混淆： #

• 按索引取值：O(1) → 直接内存访问，无需搜索
• 按值查找（无序数组）：O(n) → 需要线性遍历

内容的提问来源于stack exchange，提问作者Martin Muldoon