[자료구조] 시간 복잡도(Time Complexity)

알고리즘의 성능을 구하기 위해 실제 시간을 재는 것도 물론 좋은 방법이다만 수학적 혹은 이론적으로 접근하여 이 알고리즘은 이렇다. 라고 판단을 내릴 수도 있다.  

 

선형 탐색에서의 시간 복잡도 

최선의 경우: 찾고자하는 데이터가 0번쨰 인덱스에 있음 -> 1번

 

최악의 경우: 찾고자하는 데이터가 n번째 인덱스에 있음 -> n번

 

평균의 경우: 등차수열 1부터 n까지의 합 / n -> n/2 + 1/2번

-> 찾고자하는 데이터가 0번째 값인 경우부터 n번쨰 값인 경우를 다 더하고 데이터의 개수로 나눴다. 이때 임의의 데이터 x를 찾고자 할 확률은 1/n이기 때문에 등차수열로 일반화할 수 있었다. 

 

 

Big-O(표기법)

자잘한 계산은 무시하고 배열의 크기가 엄청 커졌을 때 속도가 대략 어떤 비율로 증가하는지를 보려고 할 때 Big-O 표기법을 사용한다.

 

선형 탐색에서의 빅오 표기법

최선의 경우: 1번 -> O(1)

최악의 경우: n번 -> O(n)

평균의 경우: n/2+1/2번 ->  O(n/2+1/2)  ->  O(n)

 

 

이진 탐색에서의 시간 복잡도

최선의 경우: 찾고자하는 데이터가 (0+n) / 2 번 인덱스에 있는 경우 -> 1번 -> O(1)

최악의 경우: 배열을 2로 나눴을 떄 몫이 1이 될 때까지 나눈 횟수 -> log n + 1 -> O(log n) 

ex)

아 왜.. 그찮아. 로그 2이면 주워진 수를 2로 몇 번 나눌 수 있는지를 계산해주는 거잖아.

평균의 경우:

원소의 개수가 총 8개라고 할 때 찾고자하는 값의 인덱스가 middle 일 경우는 1개가 존재한다. 그 다음 middle 양 옆에 존재하는 값들은 2번 만에 찾을 수 있고. 다시 그 옆에 존재하는 값들은 3번만에 찾을 수 있고 4개가 있다. 그러면 마지막은 4번만에 찾을 수 있고 1개가 있다.

 

암튼 그러면 O(log n)이다.

 

자세한 수학적 증명이 궁금하다면 ...

https://sceweb.uhcl.edu/yang/teaching/csci3333fall2011/Average%20case%20analysis%20of%20binary%20search.pdf