시간 복잡도

ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84

시간 복잡도 - 위키백과, 우리 모두의 백과사전

 

what is time complexity?

시간복잡도란 무엇인가?

 

컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. 이런 방식으로 표현할 때, (예를 들면, 입력 크기를 무한대로 입력하여) 시간복잡도를 점근적으로 묘사한다고 말한다.

예시로서, 만약 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대 (어떤 n0보다 크지 않은 모든 n에 대하여) 5n3 + 3n의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(n3)이라고 할 수 있다.

시간 복잡도는 기본적인 연산을 수행하는데에 어떤 고정된 시간이 걸릴 때, 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. 그러므로 걸리는 시간의 총량과 알고리즘에 의해 수행되는 기본적인 연산의 개수는 최대 상수 인자만큼 다르다.

 

최고 차수만 남기고 싹 버린다.

예를 들어

2n^2 + n + 1 = O(N^2)

 

O(logN)

• 우선, 이진 탐색을 반복할수록 남아있는 (탐색할) 자료의 개수는 1/2로 줄어든다.
• 1번째 실행시 탐색할 남은 자료의 개수: N
• 2번째 실행시 탐색할 남은 자료의 개수: N/2
• 3번째 실행시 탐색할 남은 자료의 개수: N/2 * 1/2
• 4번째 실행시 탐색할 남은 자료의 개수: N/2 * 1/2 * 1/2
• K번째 실행시 탐색할 남은 자료의 개수: N*(1/2)^K
• 탐색이 끝나는 시점에는 남은 자료의 개수가 1이 되어야 한다. 따라서 N*(1/2)^K = 1
• 양 변에 2^K를 곱해주면 2^K = N > K = log2^N
• K의 의미는 실행횟수 따라서 자료의 갯수 N에 따른 시행횟수는 log2^N
  시간 복잡도는 BigO 표기법으로 O(logN) 으로 나타낼 수 있다.

 

간단히 유도를 해보겠습니다. 우선, 이진 탐색을 반복할수록 남아있는 (탐색할) 자료의 개수가 어떻게 될까요?

 

처음에 입력된 갯수를 N 이라하면, 

 

첫 시행 후에는 반이 버려져서 

, 

두 번째 시행 후에는 또 그 반이 버려져서 

, 

새 번째 시행 후에는 또 그 반이 버려져서 

,

 

규칙이 보이시나요? 그렇습니다. 매 시행마다 탐색할 자료의 개수가 점점 반씩 줄어드는 걸 알 수 있죠.

 

그럼 K 번의 시행 후에는? 

개가 남게 되겠죠.

 

이렇게 계속해서 탐색을 반복하다보면 탐색이 끝나는 시점에는 (최악의 경우 즉, 찾는 데이터가 없는 경우) 남은 자료가 1개가 남게 되겠죠.

따라서, 

라고 표기할 수 있겠군요.

 

이 때, 양 변에 

 을 곱해주면 

마지막으로 양 변에 2를 밑으로 하는 로그를 취해주면, 

 

잠시, 그럼 여기서 K의 의미가 뭐였었죠? 그렇습니다 바로 시행 횟수였었죠.

 

즉, 자료의 갯수 N에 따른 시행 횟수는 

, 따라서 시간 복잡도는 Big O 표기법으로 

 로 나타낼 수 있겠습니다.

(상수 부분은 무시하기 때문에)

 

 

O(N)

for문 한번

 

O(NlogN)

병합정렬(Merge sort, heap sort 등)

 

O(N^2)

삽입정렬, 선택정렬, 버블 정렬 등

 

O(N^3)