complexity-theory - 平均计算最坏情况、最佳情况和平均情况复杂度

Question

以下计算平均值的函数的 (a) 最坏情况、(b) 最佳情况和 (c) 平均情况复杂度是多少

n=0
sum=0
input(x)
while x!=-999 do
    n=n+1
    sum=sum+x
    input(x)
end {while}
mean=sum/n

你会如何证明复杂性的合理性？

Answer 1

-999你一被发现就停下来。

所以：

• 最好的情况是 O(1) ：你直接找到 -999
• 最坏的情况是 O(n) -n 是input- 的大小：你-999在最后发现input
• 在这种情况下，平均情况是 O(n / 2) = O(n)：你-999在中间找到