[코테 합격자 되기] 03장. 시간 복잡도

# 알고리즘 정의

수학과 컴퓨터과학에서 사용되는,

문제 해결 방법을 정의한 '일련의 단계적 절차'이자

어떠한 문제를 해결하기 위한 '동작들의 모임'이다.

계산을 실행하기 위한 단계적 규칙과 절차를 의미하기도 한다.

즉, 문제 풀이에 필요한 계산 절차 또는 처리 과정의 순서를 뜻한다.

프로그램명령어의 집합을 의미하기도 한다.

(출처: https://ko.wikipedia.org/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

 

# 알고리즘 측정법

알고리즘을 측정하는 방법은 총 2가지로 아래와 같다

1. 절대시간 측정

문제점:

PC 환경이 모두 다르기에

기준이 되는 PC 환경을 선정해서 일반화하기 어렵다

따라서, 아래의 연산 횟수 측정을 사용한다

 

2. 연산 횟수 측정

문제점:

입력값에 따라 연산 횟수가 달라질 수 있기에 기준이 필요하다

다만, 코테에서는

최악의 경우를 기준으로 연산 횟수를 측정하는 게 합리적이라는 판단을 내렸다

 

# 시간복잡도

위처럼 코테에서는 알고리즘의 성능은 연산 횟수로 측정하고

입력값에 따라 연산 횟수가 상이하다면, 가장 최악의 경우를 기준으로 연산 횟수를 측정한다

그리고

입력값에 따른 연산 횟수를 측정해서 알고리즘의 성능을 지표로 나타낸 것을 시간복잡도라고 한다

 

# 점근적 표기법

N^2 + 3N + 5를 각 항의 그래프를 따로 그린 그래프

그래프를 보면,

특정 시점부터는 가장 최대항이 나머지 항들을 무시할 정도 커진다

따라서

1. 최고차항만 남기고

2. 최고차항의 계수를 제거하는 

점근적 표기법을 통해 시간복잡도를 나타낸다

 

# 빅오 표기법

위의 그림을 보다시피

위로 갈수록 연산 횟수가 증가하고

아래로 갈수록 연산횟수가 감소한다

해당 순서를 반드시 알아야

어떤 항이 최고차항이 되는지 알고 추출할 수 있다

 

최고차항을 추출하는 예시는 아래와 같다

 

코테에 자주 등장하는 예시 3가지는 아래와 같다

1.

2.

계속 절반으로 줄어든다 (참고로, 트리의 높이는 logN이다)

3.

2 * 2 * ... * 2 (N번까지)

 

# 최대연산 횟수

위의 연산 횟수에서

100만, 1000~2000만을 특히 기억해 두면 된다

예를 들어

문제에서 최대연산 횟수를 100만이라고 한다면,

NlogN, N, logN으로 출력해야 한다는 것이다

 

또 다른 예시를 보면,

왼쪽 문제는

최대연산 횟수를 알려주지는 않았지만,

문자열의 길이가 100만 이하이기에

100만 인 문자열이 N^2 돈다면 매우 비효율적이라는 사실을 알 수 있다

 

오른쪽 문제는

딱히 언급이 없으니

시간복잡도를 크게 신경 쓰지 않아도 된다는 것이다