algorithm - 平均情况复杂度 - 线性算法的计算

Question

只是一个简单的问题:

如果我有一个线性搜索算法(它将遍历每个元素一次直到达到特定条件)，我如何计算 n = 500 的平均情况复杂度？最坏的情况和最好的情况都很简单。

Answer 1

一般情况也同样简单:只要您找到的项目是唯一的，平均而言您将不得不查看列表的一半 + 0.5。

让我们假设您查找列表中的每个项目一次。当您查找第一项时，您将必须检查一项。当您查找第二个项目时，您将必须检查 2 个项目，依此类推。检查总数为

1 + 2 + 3 + ... + 500 = 125250

因此，通过 500 次查找，您将总共检查 125250 个项目。平均而言，每次查找需要 250.5 次检查。

如果您的查找模式不均匀，那么这将扭曲您的平均情况(例如，如果您更频繁地查找列表开头的项目，或者如果某些项目重复并且找到其中任何一个就足够了)