arraylist - ArrayList 中 Search 的时间复杂度是多少？

一个面试问题，我无法回答，也无法在网上找到任何相关答案。

我知道arraylist 根据索引在恒定时间内检索数据。

假设在一个数组列表中，有 10000 个数据并且元素位于第 5000 个位置（我们没有给出位置），我们必须搜索一个特定的值（例如整数 3，它恰好在第 5000 个索引上），用于搜索值，我们将不得不遍历数组列表来找到值，这需要线性时间，对吗？

因为如果我们遍历数组列表来查找数据，这将需要线性时间而不是恒定时间。

简而言之，我想知道 contains 方法的内部工作，我必须在其中检查特定值并且我没有索引。它必须遍历数组以检查特定值，并且需要 O(n) 时间，对吗？

提前致谢。

标签： arraylistcontains

我希望这是您想了解的有关在 ArrayList 中搜索的内容：

数组按顺序放置在内存中。这意味着，如果它是一个整数数组，每个整数使用 4 个字节，并且从内存地址 1000 开始，则下一个元素将在 1004 处，下一个元素将在 1008 处，依此类推。因此，如果我想要数组中位置 20 的元素，则 get() 中的代码必须计算：

1000 + 20 * 4 = 1080

获得元素的确切内存地址。好吧，RAM 存储器的名称为随机存取存储器，因为它们的构建方式使得它们具有硬件多路复用器的层次结构，允许它们在给定地址的情况下以恒定的时间访问任何存储的内存单元（字节？）。

因此，两个简单的算术运算和一个对 RAM 的访问被称为 O(1)。请参阅原始答案的链接。