Mean расчет худший случай, лучший случай и средняя сложность случая

Question

Что такое (а) в худшем случае (б) лучший случай, и (в) среднем случае сложность следующей функции, которая вычисляет среднее

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 (п) -п быть размером input - вы найдете -999 на самый конец input
• в среднем случае в этом случае O (п/2) = O (N): вы нашли -999 в середине