O(1) 和 O(n) 之间的线性搜索差异

Question

我在线性搜索中对以下两种情况感到困惑。先把线性搜索算法写到这里吧

线性搜索的伪代码

输入：未排序的数组 A 和键

输出：索引 i 使得 A[i] = key

LinearSearch(A,low,high,key) 
if high < low    
   return NOT_Found
if A[low] = key
   return low
return LinearSearch(A,low+1,high,key)

本书大部分内容的复杂度为 O(n)。

有什么区别

当key存在于数组中时，复杂度会降低到O(1)的原因是什么？非常感谢！

Answer 1

你的问题是基于最好的情况。最好的情况是您的密钥位于第一个位置 (O(1))。更实用的是平均情况，在这两种情况下都是 O(n)

Answer 2

What is the reason that when the key is present in the array, the complexity will reduce to O(1)?

考虑到这两种情况，数组中键的存在会有所不同：

数组中存在key:那么你的运行时间在最好的情况下 是 O(1)，这意味着您必须移动固定次数才能找到它（例如它将是第二个元素，第 10 个元素，第 1 个元素通常是常数）。如果密钥存在，那么最坏的情况是它位于数组中的 O(n) 位置，因此您至少需要 Ω(n) 步骤，当然最大步骤是搜索数组中的所有 n 个位置，因此 O(n) 证明最坏情况 Θ(n).
The key doesn't not exist：在这种情况下给定一个数组和一个不存在的键存在于数组中你的线性搜索算法试图找到它他将必须检查所有元素才能找到它因为算法有两个终止条件：找到密钥或数组有结束了。当然，在这种情况下不会找到密钥，算法将在检查所有元素后终止。这里的一个观察是，如果密钥不存在，算法将在最好或最坏的情况下执行 O(n) 个步骤，如果密钥不存在，最好和最坏的情况是相同，因为在两者中都搜索整个数组！

如前所述，在这两种情况下，最坏的情况是θ(n)。

Linear Search difference between O(1) and O(n)