인프런 커뮤니티 질문&답변

안녕하세요 반갑습니다.

음 시간복잡도를 아주 미세하게 따지지 않는다면 상수는 시간에 그렇게 많은 영향도를 미치지 못한다는 의미로 생각해주시면 됩니다.

예를들어서 N의 크기가 100인 경우 (100인 경우도 N이 그렇게 크지 않은 케이스입니다.)

만약 N에 대한 이중포문이 있다고 가정하면 N의 제곱으로 100*100 => 10000번의 반복이 발생합니다. 반면 N을 탐색하는 for문이 3~4개 있다고 하면 여기에서 발생하는 반복은 300~400번이 됩니다.

사실 컴퓨터에서는 100이나 300이나 그렇게 큰 반복문의 차이가 아닙니다.

때문에 for문이 3개있다 => 3N 4개있다 => 4N 이럴때 상수는 보통 삭제하고 해당 코드의 시간복잡도는 N정도 되겠네요. 정도로 이야기하는 것입니다. 그리고 이것이 N제곱보다 커질일은 보통 잘 없습니다.

N이 100이라면 100N == N제곱이기 때문에 for문이 100번정도 써야하는 것입니다.

NlogN?에 대한 것은 어떻지? 라고 생각해본다면 N이 100이라면 따져볼수 있겠지만 기본적으로 자바 기준 1억번의 반복을 1초로 보기 때문에 1억번이 되려면 N제곱이면 10000이 되어야 합니다.

log10000을 하여도 16번? 10번은 넘기 때문에 NlogN 시간복잡도 반복문 하나가 N시간복잡도 반복문을 10번 한것보다 더 시간을 잡아먹게 됩니다.

좀 장황하게 설명을 드린것 같은데 도움이 되셨으면 좋겠습니다!!

단 N이 매우크거나 아주 미세하게 따진다면 예외적일 수 있습니다.

만약 2천만번 도는 탐색이 10번 발생한다면?. 이런 부분을 향후 학습을 통하여 내 코드의 시간복잡도를 계산하여 보면 아마 알게 되실것 같습니다. !!

즐거운 한주 보내세요