mondegreen

[Part1-Chapter02-Clip01] 시간복잡도란 입력 크기와 알고리즘 간의 관계를 나타내는데 우리는 주로 Big-O 표기법으로 나타낸다. 문제에서 정의된 입력 데이터 중 가장 최악의 상황을 포함한 시간의 상한선을 말한다. 입력된 값과 연산을 고려했을 때 도출되는 시간복잡도 중 상수는 제외한다. 즉, O(3N+2)일 경우 3과 2는 제외하고 시간 복잡도는 O(N)이라고 말할 수 있다. 이는 입력된 값에 비례하는 시간복잡도를 가졌다는 것을 의미한다. 이를 통해 우리는 입력 크기에 대해 우리가 작성한 프로그램의 동작시간을 가늠해볼 수 있다. 아래 그래프는 n의 크기에 따른 실행속도 N을 보여주며, 표는 입력값의 범위에 따라 최대 허용되는 시간 복잡도를 대략적으로 유추한 참고 값이다. 코딩테스트에서 시..