ksshlee   4년 전

예를 들어

while(1)

이나 for(;;) 요런식이면 복잡도는 O(n)이 되는걸로 알고 있습니다

허나 만약에 

for(i=0; i<999999999; i++)

요런식으로 된다면은 무한은 아니니 복잡도는 O(1)이 되는 건가요?? 아니면 상수여도 루프가 있으니 O(n)으로 치나요??

indioindio   4년 전

무한은 아니니 복잡도가 O(1)이라기 보다는, 입력의 크기와 무관하게, 상수(999999999)번 for문을 반복하니깐 O(1)이라는 표현이 더 적절하지 않을까 싶습니다.

쓰고 보니 그게 그거 같지만요

atomzeno   4년 전

for(i=0; i<n; i++)

-->O(n)

for(i=0; i<999999; i++)

-->O(999999)=O(1)

ksshlee   4년 전

답변 감사합니다!!

그렇다면

for(i=0; i<n; i++){

       if(n==4){

             break;

              }

}

요런식으로 나오게 된다면,, 결론은 어쨌든 n번까지 돌긴 하는데 n=4에서 break 되니깐 O(1)로 표현 될수 있는건가요?? 아니면 어쨌든 루프가 무한으로 돌기 때문에 O(n)이 되는건가요??

atomzeno   4년 전

O(n)입니다

ksshlee   4년 전

ㅎㅎㅎㅎ 감사합니다 그러면 복잡도 줄이기 위해선 어떻게든 루프에 상수를 집어 넣어야 겠군요!! 감사합니다~~ㅎㅎ

indioindio   4년 전

제가 오해한 것일수도 있지만, 복잡도를 줄이기 위해 '어떻게든' 루프에 상수를 넣어야겠다는 표현은 조금 틀립니다. n을 적절한 상수로 치환한다고해서 복잡도가 줄어든다든지, 속도가 빨라진다든지 하는 것이 아닙니다.

뿐만 아니라, 그 루프가 전체적인 프로그램의 입장에서는 전채 복잡도에 영향을 주지 않을 수도 있는 것이구요.

댓글을 작성하려면 로그인해야 합니다.