시간복잡도란 연산의 수행 횟수를 의미한다.
일반적으로 컴퓨터는 1초에 1억 번 정도의 연산을 수행한다.
시간 복잡도 표기법
- 빅-오메가 표기법 : 최선일 때 연산 횟수
- 빅-세타 표기법 : 평균일 때 연산 횟수
- 빅-오 표기법 : 최악일 때 연산 횟수
코딩 테스트에서는 빅-오 표기법을 기준으로 시간 제한을 고려하는 것이 좋다. 가장 연산이 오래 걸리는 테스트 케이스를 기준으로 알고리즘을 작성한다면 나머지 테스트들은 당연히 통과 할 수 있기 때문이다.
표기 방법은 중괄호 안에 최악일 때의 연산 횟수를 적어주면 된다.
연산 횟수가 N번 이라면 O(N) , N*N 이라면 O(N*N)으로 작성한다.
시간 복잡도 계산법
시간 복잡도를 계산하는 방법은 가장 많이 중첩된 반복문의 횟수가 시간 복잡도의 기준이 된다.
또한 시간 복잡도 계산에서 상수는 무시한다.
예를들어 데이터의 개수인 n = 1억 이라고 생각해보자.
- O(n*n) = 1억 x 1억
- O(n) = 1억
1억 이라는 상수는 그 자체로 유의미한 값이라고 생각 할 수 있지만 시간 복잡도가 O(n*n)인 1억 x 1억 의 값과 비교했을때 충분히 무시해도 될 만큼 작은 값이다.
그렇다면 여기서 1억에 100을 곱하면 어떨까?
- O(n)
- O(100*n)
위의 두 값은 유의미한 차이가 있을까?
물론 n 앞의 상수가 n의 값보다 커진다면 n*n 보다 커지므로 유의미한 값이 될 수 있다.
하지만 n =1억 인데 앞의 상수가 10 이라고 해서 두 시간 복잡도 사이에 큰 차이가 있지는 않을 것이다.
따라서 시간 복잡도를 계산할때는 가장 많이 중첩된 반복문 을 기준으로 생각하자.
그렇다면 우리는 왜 코딩 테스트를 볼 때 시간 복잡도를 고려해야할까?
알고리즘 선택의 기준
코딩 테스트의 경우에는 데이터 개수와 시간 제한이 주어지기 때문에 제한 시간 내에 연산을 할 수 있도록 시간 복잡도를 고려하여 알고리즘을 선택 하는 것이 중요하다.
예를들어 데이터의 개수가 100만이고 제한 시간이 1초라고 하자.
여기서 시간복잡도가 O(n*n)인 알고리즘을 사용한다면 문제를 통과 할 수 있을까? 출력 결과는 맞을 수 있어도 시간 초과로 인해 틀리게 될 것이다. 단순히 출력값이 일치 한다고 해서 통과 할 수 없다
이런 경우에는 O(n*logn) 이하의 시간 복잡도의 알고리즘을 선택해서 코드를 작성해야 문제를 풀 수 있을 것이다.
코딩 테스트 문제를 풀때는 데이터 개수와 시간 제한을 생각하여 어떠한 시간 복잡도를 가지는 알고리즘을 쓸 지 선택하는 것도 중요하다
비효율적인 코드의 로직 수정
만약 작성한 코드가 시간 초과로 틀렸다면 시간 복잡도를 고려하여 어디에서 가장 연산이 많이 걸렸는지를 생각하고
더욱 코드를 효율적으로 작성 할 수 있을 것이다.
시간 초과로 문제를 틀렸다면 가장 연산이 많이 걸리는 부분의 코드를 수정해야지 괜히 출력을 더 빨리하는 방법을 쓰도록 수정 한다고 해서 테스트를 통과 할 수는 없을 것이다. 비효율적인 부분을 개선하는 것이 가장 효율적인 방법이다.