有人能告诉我线性搜索应用于排序数组时的平均时间复杂度是多少？我知道最坏的情况是O（n），最好的情况是O（1），但我不知道排序数组中的平均情况。
让我们假设在数组中有n个元素。然后，我们知道平均情况总是在概率论上起作用，即假设在每个位置搜索或找到一个元素的概率是相同的，那么在这种情况下，由于我们有n个元素，所以概率为1 / n ...
现在，为了成功搜索：
我们可能需要执行1个比较或2或3或4，依此类推..
因此complexity(successful search) = 1（1 / n）+ 2（1 / n）+ 3（1 / n）..... n（1 / n）=（n + 1）/ 2
还考虑搜索失败：
complexity(unsuccessful search) = n（因为在考虑失败之前，我们将研究所有数组）。
现在，如果“ q”是成功概率，则“ 1-q”将是失败概率。
因此，平均复杂度 = q *（n + 1）/ 2 +（1-q）* n
这里，q = 1/2
平均复杂度 =（3n + 1/4）〜O（n）