algorithm - 访问和搜索数组有什么区别？

Question

在学习数据结构和算法时，我同时遇到了这两个术语，但我无法区分访问和搜索。例如数组的时间复杂度，访问时间为O(1)，搜索时间为O(n)。

Answer 1

让我们想象一条街道，我们称之为 List Street。在 list 街上，有房子。第一所房子的地址是 101 List Street。第二间房子的地址是102 List Street。等等等等。

假设我们知道我们的 friend Element 住在 List Street 的 4th house，那么我们知道 Element 必须住在 List Street 104。我们可以立即访问他们的房子，因为我们确切地知道它在街上的位置。我们只需要访问 1 个房子就可以找到 Element。

但是如果我们不知道 Element 住的房子怎么办？我们必须敲每户人家的门，询问 Element 是否住在那里。在这种情况下，我们需要访问 4 栋房屋，直到到达 104 List Street 才能找到 Element。

同样的想法也适用于数组。数组存储数据类型。每种数据类型的大小都相同，例如 int 通常是 4 个字节。如果 int 数组从内存地址 0x0001 开始并且我们想要访问任何元素，则访问 array[2] 需要相同的时间> 和 array[102] 一样，和 array[9999] 一样。因为我们知道起始地址，也知道每种数据类型的大小，所以我们可以立即跳转到内存中的那个位置。 O(1)

但是，如果您尝试搜索 特定元素，则需要访问每个元素并测试它是否是您要查找的元素，直到找到所需元素。对于包含 5 个元素的数组，您可能需要搜索 5 次。 O(5)。对于包含 900 个元素的数组，您可能需要搜索 900 次才能找到所需的元素。 O(900)。对于包含 n 元素的数组，您将搜索 n 次。 O(n)