DSA 线性查找时间复杂度

请查看 此页面 以获取有关时间复杂度的常规解释。

线性查找时间复杂度

有关时间复杂度的详细说明，请访问 此页面。

有关插入排序时间复杂度的更全面和详细的解释，请访问 此页面。

线性查找 将每个值与其要查找的值进行比较。如果找到该值，则返回索引，如果未找到，则返回 -1。

为了找到线性查找的时间复杂度，让我们看看是否可以找出在包含 \(n\) 个值的数组中查找一个值需要多少次比较操作。

最佳情况是如果我们正在查找的值是数组中的第一个值。在这种情况下，只需要进行一次比较，时间复杂度为 \(O(1)\)。

最坏情况是如果遍历整个数组而没有找到目标值。在这种情况下，数组中的所有值都与目标值进行比较，时间复杂度为 \(O(n)\)。

平均情况并不容易确定。找到目标值的可能性是多少？这取决于数组中的值，对吧？但是，如果我们假设数组中的值只有一个等于目标值，并且该值的的位置可以在任何地方，那么线性查找所需的平均时间是最坏情况所需时间的一半。

线性查找的时间复杂度为 \(O(n)\)。

如果我们绘制线性查找在包含 \(n\) 个值的数组中查找一个值所需的时间，我们将得到此图

线性查找模拟

针对数组中不同数量的值运行模拟，并查看线性查找在包含 \(n\) 个值的数组中查找一个值需要多少次比较。

如您在运行线性查找模拟时所见，如果快速找到该值，则搜索需要少量比较，但如果未找到我们正在查找的值，则会执行最大次数的比较。