big-o - 不执行时的时间复杂度

Question

以下程序段的“最佳情况”时间复杂度是多少？

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

当用户第一次输入“-999”时，“最佳情况”是否可能是 O(1) 注意：当用户第一次输入 -999 时，“均值”将为 0/0，函数结果未定义

Answer 1

最坏的情况是无穷大，这意味着这个程序永远不会停止。我什至不会称它为算法，因为“算法”的某些定义需要一组有限的输入，而另一些则要求它在给定数量的计算步骤之前终止。

这意味着O()在这里不适用。

Answer 2

算法的复杂性通常是根据某种数据来定义的。它可以是输入数据，就像你的情况一样。

想象一下，数据不是手动输入的，而是在应用程序中以数组的形式提供的。那么复杂度会是多少呢？

在这种情况下，处理的数字数量为 N，每个 N 循环运行一次，因此您可以假设复杂度为 O(N)。