그동안 기초없이 개발을 하고있었다는 느낌이 많이들어서 알고리즘의 기초부터 닦아 올라가려고한다.

시간복잡도

알고리즘의 선택의 기준은 시간복잡도이다.

알고리즘에서 시간복잡도는 주어진 문제를 해결하기 위한 횟수를 말한다. 일반적으로 수행시간은 1억번의 연산을 1초의 시간으로 간주하여 예측한다.
ex) 시간제한 2초 -> 2억연산안에 답이나와야 한다.

시간복잡도의 유형

• 빅-오메가(Ω(n)) : 최선(best case)일 때의 연산 횟수를 나타낸 표기법 (best case)
• 빅-세타(Θ(n)) : 보통(average case)일 때의 연산 횟수를 나타낸 표기법
• 빅-오(O(n)) : 최악(worst case)일 때의 연산 횟수를 나타낸 표기법

코딩테스트에서 사용해야하는 시간복잡도 유형

• 코딩테스트에서는 빅-오(O(n)) 표기법을 기준으로 수행시간을 계산하는것이 좋다.
• 한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단하므로 시간복잡도를 판단할 때는 최악일 때를 염두에 두어야한다.

연산횟수 계산 방법

- 연산횟수 = 알고리즘 시간 복잡도 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. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이된다.

시간복잡도의 활용

시간 복잡도를 사용하면 실제 코딩테스트에서 시간초과가 발생했을 때 이 원리를 바탕으로 문제가 되는 코드를 도출 할 수 있고, 이부분을 연산에 더욱 효율구조로 수정하는 것으로 문제를 해결 할 수 있다.
또한 시간복잡도에 따라 알맞은 알고리즘을 선택할 술 있고 비효율적인 로직을 찾아서 효율적으로 바꿀 수 있다.

참조
DO it!알고리즘 코딩테스트 with JAVA