for 가 while 보다 빠른 이유는? (시간복잡도)

아 이런 기초적인것은 진짜 잘안다고 생각했는데..

글쎄 울 교수중에 겜업체에서 강사하러 오신분이 있는데..

그 분말이 for 문이 while 보다 빠르답니다... 아 충격!!

저도 언어는 좀 한다 생각했는데..

"둘중 어떤게 더 빠를까요?" 하는 순간... 당황..

다른 교수들의 그런 황당질문(예를 들어 1을 10으로 나누고 10으로 곱하면 얼마냐? 하는등등 = 0.999..)

은 다 대답했었는데.. 이건 감이 안잡히더군요..

작은소리로 while 문이 아주 약간 빠르지 않을까요?

그 교수가 그러더군요... 당당하게..

절대 아님... while 이 시간복잡도 측면에서 빠름..

간단한 경우에는 차이가 안나지만 복잡해질수록 for 문이 유리하다는데..

아 이해가 안갑니다. 왜 그럴까요?

설마 이중 삼중 겹칠때 변수가 좀더 지역적인가 아닌가를 두고 하는 말일까요?

그거라면 좀 감은 가는데..

제가 시간복잡도라는 말을 처음들어 놔서 당황했습니다.

둘의 속도를 증명하는게 어려우시다면 시간복잡도에 대해서 아주 쉽게 설명해주셔도 감사합니다.

-----------------------------------------------------------------------------------

안 그렇습니다. while 이 for 보다 빠르다고도, for 가 while 보다 빠르다고도 말할 수 없습니다. (에, 그리고 시간 복잡도는 이 문제랑은 하등 관계 없습니다.)

이론상으로 볼 때, 모든 for 루프는 while 루프로 전환할 수 있습니다.

for (expr1; expr2; expr3) { /* body */ }
expr1; while (expr2) { /* body */ expr3; }

반대로 모든 while 루프는 for 루프로 전환할 수 있습니다.

while (expr) { /* body */ }
for (; expr; ) { /* body*/ }

따라서 이상적으로는 이 둘 사이에 속도 차이가 생길 수도 없고 생겨서도 안됩니다.

그러나, for 루프로 프로그래밍하다 보면 while 루프를 쓸 때보다 필요 없는 내용을 더 집어넣기 쉽습니다. 예제로 kurishin 님의 답변 중 세번째를 봅시다. 어셈블리는 빼고 C 코드만 씁니다.

i = 100; while(i--);
for(i=100; i >=0; i--);

이 두 루프는, 서로 *다른* 루프입니다. 간단히 봐도, while 쪽은 (i-- != 0) 이 루프 조건인데 반해 for 쪽은 (i >= 0) 이 조건입니다. (그런 이유로, 사실은 도는 회수마저도 while 은 100 번이지만 for 는 101 번입니다. -_-) 위 while 루프와 같은 for 루프는 다음 루프입니다.

for(i=100; i--; );

이 쪽은 컴파일하면 (GCC 3.2.2 로 최적화 금지하여 테스트하였음) 앞의 while 루프와 같은 기계어 코드를 만듭니다. 하지만 kurishin 님의 for 루프는 그와 다른 기계어 코드를 만들게 되는데, while 쪽에는 i-- 만 있는 반면 for 루프 쪽에는 i-- 외에도 i >=0 이 더 붙어 있으니 for 루프 쪽의 코드 크기가 더 커지겠죠. 그래서 for 루프가 더 느릴 '수도' 있습니다.

하지만, for 루프는 while 루프보다 구조가 더 잘 짜여져 있기 때문에, 멍청한 컴파일러라면 while 은 잘 이해 못하면서 for 는 이해할 가능성이 있을지도 모릅니다. 그럼 for 루프 쪽이 조금 더 빠른 코드가 되겠죠. 이런 경우가 혹시 있다면 for 가 더 빠를 '수도' 있습니다. 예를 들어, loop unrolling 이라는 최적화 기법을 적용할 경우에는 for 루프 쪽이 월등히 편하다고 합니다.

사족입니다만 loop unrolling 이 나온 김에 언급해두자면, 큰 루프라고 더 느리다는 법도 없습니다. 이 기법은 메모리 사용량을 속도와 맞바꾸는 방법입니다. 즉 루프가 커지는데 더 빨라지는 거죠. 대표적인 예로, 다음 루프

do {
*to = *from++;
} while(--count>0);

보다 다음 루프

// Duff's device
register n=(count+7)/8;
switch(count%8){
case 0: do{ *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
} while(--n>0);
}

가 더 빠를 수도 있습니다. (뭐, 물론 그렇다는 보장 또한 없습니다.)

뭐, 그래서 for 가 빠를 수도 있고 while 이 빠를 수도 있고 이럴 수도 있고 저럴 수도 있다면 도대체 결론이 뭐냐? 싶으실 수도 있을 겁니다. 그런데 그 답은 이미 컴퓨터 공학계에 격언처럼 전해 내려오지요. (... 전 컴공이랑 관계 없습니다만 --;;)

"Premature Optimization is the Root of All Evil"
번역하자면 "섣부른 최적화는 만악의 근원" 정도.

간단히 말해, 근거 박약한 가정은 아예 하지도 말라는 얘깁니다. for 가 while 보다 빠르다고요? 어느 시스템에서인지, 어느 컴파일러에서인지, 어떤 코드에서인지, 몇 %나 더 빠른지, 무엇 때문에 더 빠른지, 확실해지기 전에는 그렇게 믿어선 안됩니다. 실제 환경에서 프로파일링해 보기 전에는 모르는 겁니다. 그 강사분의 경험에서는 정말로 for 가 while 보다 빨랐을 수도 있지만, 그게 언제나 옳다는 보장은 전혀 없습니다.

출처 : http://kin.naver.com/db/detail.php?d1id=1&dir_id=10104&docid=283394