더북(TheBook)

 

SECTION 2.2 시간 복잡도 계산하기

앞서 시간 복잡도의 개념과 사용되는 상황을 어느 정도 이해했다면 몇 가지 의문이 생깁니다.

첫째, for 문을 2번 중첩하면 무조건 O(n2)이고, 3번 중첩하면 무조건 O(n3)인가요? 둘째, 빅오 표기법은 최고 차항만 신경 쓴다고 했는데 만약 n2과 999999n이라면 둘 중 누가 더 빠른가요? 셋째, 앞으로 자주 사용할 알고리즘의 시간 복잡도는 어느 정도일까요?

이 의문은 코드가 어느 정도의 시간 복잡도를 가지는지 예측하기 어렵다는 것에서 비롯됩니다. 코드의 실행 시간을 예측하려면 많은 연습과 경험이 필요하고, 이 외에도 수많은 변수가 있기 때문에 알고리즘에 능통하더라도 예측하기 쉽지 않습니다. 지금부터는 경험이 없더라도 코드의 시간 복잡도를 예측할 수 있는 몇 가지 사항을 알아보겠습니다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.