시카로의 공부방

시간 복잡도는 알고리즘의 성능을 나타내는 지표다. 해당 알고리즘을 실행시켰을 때, 연산 횟수에 대한 worst case적인 한계를 의미한다. 시간 복잡도는 낮으면 낮을 수록 좋다. 빅 O 표기법을 통해 알 수 있으며, 현대 컴퓨터에서 대략적으로 1초 연산이 최대 1억번의 연산 횟수를 가진다는 걸 머릿속에 넣어 놓으면 좋다. 이를 통해 우리는 조건이 1초, 1만개가 들어가는 테스트 케이스 범위가 주어졌을 때, O(n^2)은 쓰지 못한다는 걸 직감적으로 알 수 있게 된다. 시간을 측정하려면 절대 시간을 측정하는 방법도 있으나, 그런 방법은 코딩 테스트에서는 잘 활용되지 않는다. 빅오 표기법 1차원 배열에서 가장 값을 늦게 찾는 경우는 리스트의 끝까지 검색했을 때 혹은 값을 못찾았을 때. 즉, O(n)이다. ..