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

如果我有一个线性搜索算法（它会经过的每一个元素，一旦达到一定的条件下），我怎么能计算出平均情况复杂对于n = 500？最坏的情况和最好的情况很容易。

如果它是线性计数，它不会只是250吗？ – joshstrike

平均情况同样很简单：只要你发现的物品是独一无二的，平均来说，你将不得不在查看列表+ 0.5的一半。

让我们假设你查看列表中的每个项目一次。当你查找第一个项目时，你将不得不检查一个项目。当你查看第二个项目时，你将不得不检查2个项目，等等。检查总数为

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

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

如果您的查找模式不均匀，那么这会使您的平均情况偏差（例如，如果您更频繁地查找列表开头的项目，或者某些项目被重复查找并找到其中任何项目就足够了）

2013-11-01 10:49:49 tfinniga

是的，这就是我的想法，但我记得因为某种原因，我的老师在讲座中说这是不正确的。不过，这对我来说很合理。谢谢！ – user1062704

当我真正计算复杂性时，让我感到吃惊的是，答案是250.5而不是250. – tfinniga

如果它令人惊讶，你只需记住基本算术系列（1 + 2 + ... + n）之和的公式，。这是（术语数）*（第一学期+上学期）/ 2。既然你把这个总和除以项数，你计算的只是（第一项+上一项）/ 2。在这种情况下（500 + 1）/ 2 – Shashank

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

2014-11-23 13:22:17

回答