[CS,코딩테스트] 코딩테스트의 시간 복잡도에 관하여

시간 복잡도 표기법 알아보기

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다.

일반적으로 수행시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측합니다.

 

빅-오메가: 최선일 때의 연산 횟수를 나타낸 표기법

빅-세타: 보통일 때의 연산 횟수를 나타낸 표기법

빅-오: 최악일 때의 연산 횟수를 나타낸 표기법

 

예로, for loop를 0~100 까지 반복하는 코드가 있고, if 문을 통해 return하는 함수가 존재할때,

최선일 때 - 1회만에 바로 성공 - 빅-오메가

보통일 때 - 50회에 성공 - 빅-세타

최악일 때 - 100회 마지막에 성공 - 빅-오

 

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

코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋습니다.

 

왜냐하면,

보통 코딩테스트는 1개의 테스트 케이스로 합격, 불합격을 정하지 않고 많은 테스트 케이스를 넘어서

합,불합이 정해지기 때문에 가장 최악의 경우까지 통과한다면, 모두 만족시키는 코드가 될 것이고,

이러한 경우때문에 빅-오 표기법을 기준으로 계산합니다.

 

각 알고리즘마다 시간복잡도가 존재하는 것을 차차 확인 할 수 있습니다.

 

실제 코딩테스트에서 시간복잡도를 따지는 케이스?

두가지 케이스가 존재,

1. 알고리즘 유형에 따라서

2. 자기가 짠 코드가 시간복잡도가 과연 몇인지? 따져볼 수 있습니다.

 

시간복잡도를 따져보기

n의 개수가 주어졌을때 이를 오름차순 정렬하는 프로그램을 작성하시오

 

시간복잡도를 따질 때에는 먼저 데이터의 개수를 확인한다.

 

ex) 1번째 줄에 수의 개수 n(1 <= n <= 1,000,000) -> 100만개의 데이터가 존재

시간 제한이 2초라고 가정했을때,

이 조건을 만족하려면 1초당 1억번의 연산이 가능하다고 염두해두고

2억번의 요청을 받아낼 수 있는 알고리즘을 짜면 된다.

 

빅-오 표기법 기준으로 가장 최악의 경우의 수가 성공하는 케이스라면 그것은 통과하는 코드라고 생각하면 된다.