algorithm - 平均案例复杂度 - 线性算法的计算

Question

只是一个简单的问题：

如果我有一个线性搜索算法（它将遍历每个元素一次直到某个条件），我如何计算 n = 500 的平均案例复杂度？最坏的情况和最好的情况很容易。

Answer 1

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

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

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

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

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

Answer 2

线性搜索算法的平均案例复杂度为 n+2，其中 n 是列表中元素的数量。