그동안 기초없이 개발을 하고있었다는 느낌이 많이들어서 알고리즘의 기초부터 닦아 올라가려고한다.
알고리즘에서 시간복잡도는 주어진 문제를 해결하기 위한 횟수를 말한다. 일반적으로 수행시간은 1억번의 연산을 1초의 시간으로 간주하여 예측한다.
ex) 시간제한 2초 -> 2억연산안에 답이나와야 한다.
- 연산횟수 = 알고리즘 시간 복잡도 X 데이터의 크기
- 버블정렬 = (1,000,000)^2 = 1,000,000,000,000 > 200,000,000 -> 부적합 알고리즘
- 병합정렬 = 1,000,000log(1,000,000) 약 20,000,000 < 200,000,000 -> 적합 알고리즘
1. 상수는 시간복잡도에서 제외 ( Ex : O(3N) -> O(N) 과 같은 것으로 본다.)
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이된다.
시간 복잡도를 사용하면 실제 코딩테스트에서 시간초과가 발생했을 때 이 원리를 바탕으로 문제가 되는 코드를 도출 할 수 있고, 이부분을 연산에 더욱 효율구조로 수정하는 것으로 문제를 해결 할 수 있다.
또한 시간복잡도에 따라 알맞은 알고리즘을 선택할 술 있고 비효율적인 로직을 찾아서 효율적으로 바꿀 수 있다.