0

（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

複雑さをどのように正当化しますか？

4

1 に答える 1

1

見つかったらすぐに停止し-999ます。

したがって：

  • 最良のケースはO（1）です：-999を直接見つけます
  • 最悪の場合はO（n）-nはinput-のサイズです：あなたは-999の最後にありますinput
  • 平均的なケースはその場合ですO（n / 2）= O（n）：あなた-999は真ん中に見つけます
于 2013-03-06T13:22:05.533 に答える