[코딩테스트] No.1 알고리즘 효율 분석(시간복잡도)-3장

코딩테스트 준비를 하기 위해서 연습 문제를 풀때, 제한 시간을 한번쯤 볼 수 있었을 것이다. 

여기서 말하는 제한 시간은 알고리즘이 실행되고 종료될 때 걸리는 시간의 제한 시간을 말하는 것이다. 

 

컴퓨터에서 1초당 처리되는 연산 횟수가 대략적으로 정해져있다.

 

(코딩테스트를 치는 환경(연습으로 문제푸는 환경도 마찬가지)에는 모든 컴퓨터의 성능이 동일하다고 가정한다. )

(1초당 1억개의 연산 가능)

 

그런데 문제에 대해 알고리즘을 어떻게 짜냐에 따라서 1초당 처리되는 연산 횟수가 줄어들 수도 있고 유지될 수도 있다. 

더 많아질 수는 없다. (컴퓨터가 자가 발전하지 않는 이상(?))

 

코드를 작성하고 나서 이 알고리즘이 어떻게 짜여졌냐? 어떻게 짜여졌길래 1초당 처리되는 연산 횟수가 이런가?

 

작성한 알고리즘이 1초당 처리되는 연산 횟수가 이정도면 대략 이정도의 복잡도를 가진 알고리즘일 것이다. 

(단, 입력 크기를 N으로 일반화 해야함. 왜냐하면 입력 크기가 1인 경우 알고리즘을 작성해야 하는 경우로 예를 들자면, 입력크기가 1일때만  연산 횟수가 1인 성능을 가지는 것이기 때문 == 해당 상황에 한정된것, 입력 크기가 다른 값으로 바뀔경우 연산 횟수 성능도 바뀔 것)

 

이런 맥락에서의 복잡도를 가지고,

==> 우리는 이것을 알고리즘의 시간복잡도라고 하기로 했다. 

 

---

 

입력 크기에 따른 연산 횟수 추이를 활용해 시간 복잡도를 표현하는 방법을 점근적 표기법이라 한다. 

 

[시간 복잡도(time complexity)]

: 알고리즘의 성능을 나타내는 지표. 입력 크기(알고리즘이 처리해야 할 데이터의 양)에 대한 연산 횟수의 상한을 의미한다. 

시간 복잡도는 낮으면 낮을 수록 좋다. 

 

시간 복잡도는 최선, 보통, 최악의 경우로 나눌 수 있지만, 코딩테스트에서는 작성한 알고리즘의 최악의 경우를 고려하여 시간 복잡도를 계산해야한다. 왜냐하면, 모든 경우의 수에서 알고리즘이 문제를 처리하는 것을 고려해야 하기 때문이다. 

 

* 빅오 표기법

: 빅오 표기법은 최악의 경우일 때의 시간 복잡도를 표현하는 방법이다. 

빅오 표기법은 특정 알고리즘의 연산 횟수가 f(x)일 때, 함수의 최고차항만을 남기고 남은 자수를 지워 O(최고차항)와 같이 표현하면 된다. 

 

 

* 빅오 표기법을 쉽게 쓸 때 최고차항만 남기고 차수를 지우는 이유

: 시간복잡도 식에서 최고차항 이외의 값들을 2차원 그래프에서 표현해보면 최고차항 이외의 값들은 무시할 수 있을 정도로 작으므로 무시한다. 

 

컴퓨터는 1초에 최대 1억번 연산할 수 있다. 

 

코딩 테스트의 문제는 출제자의 의도대로 로직을 구현했을 경우 대부분 코드를 정답처리 할 수 있게끔 채점시간을 정한다. 

 

 

시간 복잡도	N의 가용 범위
O(N!)	10
O(2^N)	20~25
O(N^3)	200~300
O(N^2)	3,000~5,000
O(NlogN)	100만
O(N)	1,000~2,000만
O(logN)	10억

 

 

이때, 언어별로 다른 성능의 차이는 고려하지 않는다. 

 

 

[시간 복잡도 계산해보기]

: 과정

1. 문제 정의

2. 연산 횟수 측정

3. 시간 복잡도 분석

 

* 고려할 점

출력 자체도 연산이다. 

비교도 연산이다. 

 

 

 

 

 

 

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)