무한은 아니니 복잡도가 O(1)이라기 보다는, 입력의 크기와 무관하게, 상수(999999999)번 for문을 반복하니깐 O(1)이라는 표현이 더 적절하지 않을까 싶습니다.
쓰고 보니 그게 그거 같지만요
무한은 아니니 복잡도가 O(1)이라기 보다는, 입력의 크기와 무관하게, 상수(999999999)번 for문을 반복하니깐 O(1)이라는 표현이 더 적절하지 않을까 싶습니다.
쓰고 보니 그게 그거 같지만요
제가 오해한 것일수도 있지만, 복잡도를 줄이기 위해 '어떻게든' 루프에 상수를 넣어야겠다는 표현은 조금 틀립니다. n을 적절한 상수로 치환한다고해서 복잡도가 줄어든다든지, 속도가 빨라진다든지 하는 것이 아닙니다.
뿐만 아니라, 그 루프가 전체적인 프로그램의 입장에서는 전채 복잡도에 영향을 주지 않을 수도 있는 것이구요.
댓글을 작성하려면 로그인해야 합니다.
ksshlee 4년 전
예를 들어
while(1)
이나 for(;;) 요런식이면 복잡도는 O(n)이 되는걸로 알고 있습니다
허나 만약에
for(i=0; i<999999999; i++)
요런식으로 된다면은 무한은 아니니 복잡도는 O(1)이 되는 건가요?? 아니면 상수여도 루프가 있으니 O(n)으로 치나요??