시간 복잡도의 개념과 코딩 테스트에서의 활용법

1. 시간 복잡도 란?

(1) 개념

시간 복잡도는 주어진 문제를 해결하는데 필요한 연산 횟수를 말한다.

(2) 표기 방법의 종류

시간 복잡도를 표기하는 방법에는 다음의 3 가지가 있다.

이름	설명
빅-오메가 표기법	문제를 풀기 위해 주어진 상황이 최선의 상황일 때 필요한 연산 횟수를 나타내는 표기법
빅-세타 표기법	문제를 풀기 위해 주어진 상황이 보통의 상황일 때 필요한 연산 횟수를 나타내는 표기법
빅-오 표기법	문제를 풀기 위해 주어진 상황이 최악의 상황일 때 필요한 연산 횟수를 나타내는 표기법

예를 들어 설명

1~100의 숫자가 랜덤한 순서로 저장된 배열이 주어졌을 때, 해당 배열에서 56의 INDEX를 찾아서 출력하라 라는 문제를 풀어야 한다고 하자.

이때 내가 선택한 방법은 배열의 첫 번째 인덱스부터 일일히 조회이다.

빅-오메가 표기법으로 연산 횟수를 나타냈을 때, 연산 횟수는 1이다. 최선의 상황에서는 56이 배열의 0 번째 인덱스에 존재할 것이기 때문에, 연산을 한 번만 해서 56을 찾고, 그 인덱스인 0을 출력할 것이다.

빅-세타 표기법으로 연산횟수를 나타냈을 경우, 연산 횟수는 50이다. 보통은 평균을 말한다. 최선의 경우가 연산을 1 번만 하는 것이라면, 최악의 경우는 연산을 100 번 전부 하는 것일 것이다. 따라서 평균의 경우에 드는 연산의 횟수는 50이다. 만약 문제가 1~N 의 숫자 중에 56의 INDEX를 출력하는 것이었다면, 빅 세타 표기법으로 나타낸 연산 횟수는 N/2 였을 것이다.

빅-오 표기법으로 연산횟수를 나타냈을 경우, 연산 횟수는 100번이다. 최악의 상황을 가정한다면 56이 배열 맨 끝에 있어서 모든 배열의 원소를 조회해야지만 찾을 수 있을 것이다. 만약 숫자가 N개 주어진다면 N번을 조회하여야 한다.

• 알고리즘 문제를 풀 때는 당연하게도 빅-오 표기법을 많이 활용한다. 최악의 상황에서도 문제에서 제시한 시간 초안에 문제를 해결할 수 있어야 하기 때문이다.

(3) Big-O 표기법 연산 횟수의 유형

위의 표는 주어진 데이터 크기(N)에 따라 필요한 Big-O 표기로 나타낸 연산 횟수이다.

N에 적당한 수를 집어넣어서 생각해보면, 왜 각 factorial이 시간이 제일 많이 들고, logN 이 시간이 제일 적게 드는지 알 수 있을 것이다.

2. 코딩 테스트에서 시간 복잡도 활용법

코딩 테스트에서 문제 별로 제한 시간(초)가 주어진다. 일반적으로 1초 당 1억 번의 연산이 가능하다고 가정한다.
만약 문제에서 2 초가 주어졌다면, 총 2억 번의 연산이 가능한 것이다.

주어진 데이터 크기에서 드는 Big-O 시간 복잡도가 문제에서 주어진 Maximum 연산 횟수보다 작다면 해당 알고리즘을 이용해서 문제를 풀어도 되는 것이다.

예를 들어 N <= 1,000,000 이고, 2 초가 주어졌다면 N^2 의 시간 복잡도가 드는 알고리즘의 경우, 연산 횟수가 1,000,000,000,000 번이 들어서 사용하지 못한다. 하지만 NlogN의 시간 복잡도가 드는 알고리즘의 경우, 20,000,000 번의 연산 횟수가 필요하므로 2억 번 내로 충분히 계산이 가능해서 사용 가능하다.