실행하지 않는 경우 시간 복잡도

Question

다음 프로그램 세그먼트의 "가장 좋은 경우"시간 복잡도는 무엇입니까?

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

는 "최상의 경우"O 될 수 있는가 (1) 처음 유형의 사용자가 "-999" 참고 때 : 처음에 사용자 유형 -999이 "의미"때 0/0이 될 것입니다, 함수의 결과가 정의되지 않았습니다.

Answer 1

알고리즘의 복잡도는 일반적으로 어떤 종류의 데이터와 관련하여 정의됩니다. 그것은 귀하의 경우와 마찬가지로 입력 데이터가 될 수 있습니다.

데이터가 수동으로 입력되지 않지만 앱의 배열에 제공된다고 잠시 상상해보십시오. 그렇다면 그 복잡성은 무엇입니까?

이 경우 처리되는 숫자의 양은 N이며 루프는 각 N에 대해 한 번 실행되므로 복잡도가 O (N)라고 가정 할 수 있습니다.

Answer 2

최악의 경우는 무한대이며, 이는이 프로그램이 절대로 멈추지 않는다는 것을 의미합니다. "알고리즘"의 일부 정의는 한정된 입력 집합을 요구하는 반면, 다른 알고리즘은 주어진 계산 단계 이전에 종료되어야한다고 요구하기 때문에 알고리즘이라고 부르지 않을 것입니다.

즉 O()은 여기에 적용되지 않습니다.