use*_*752 5 algorithm asymptotic-complexity
我对找到平均案例复杂度感到非常迷茫，只是提出了一个随机问题......就像。
对于标记顺序搜索，如果概率为 0 <= p <= 1，则找到平均情况。
我得到最坏的情况是 O(n+1)，因为数组中有 n 个元素加上你在最后添加的键的额外元素。如果您立即找到它，最好的情况就是 O(1)。
我真的不想要答案......但更多如何......如果我只是想要答案，我想我只是看看解决方案手册。
你是对的，“平均情况复杂性”需要仔细定义算法和可能的输入集。
搜索整数线性列表所需的比较次数提供了一个示例。
如果输入的搜索键可以是任意整数，则平均结果是搜索整个列表（需要 n+1 次比较才能找到哨兵），因为整数有无限多个，而数组中的元素只有有限个。只有有限数量的输入需要少于 n+1 次比较，但无限多个输入将导致 n+1 次比较。
另一方面，如果分析是从数组中的元素（均匀）随机选择搜索关键字（并且这些元素不包含重复）时的平均比较次数，则可能结果的平均值将是比较次数当搜索到的项目在列表中第一个时加上它在列表中第二个时的数字，依此类推，直到第 n 个项目，全部除以结果数，即 n。换句话说，
(1 + 2 + ... n) / n = n(n+1)/(2n) = (n + 1) / 2
这是一个健全性检查：令 n=1。那么公式表示在 1 元素列表中查找元素的平均比较次数为 1。这显然是正确的。
最后一点是，你提出问题的方式表明你应该研究大 O 的定义。O(n) 与 O(n+1) 相同。大 O 始终是所测量的上限的表达式。表达平均值的上限通常是不合适的，因为平均案例分析通常也提供下限。在平均情况下，上面的 (n+1)/2 比较最好表示为 \Theta(n)。