[자료구조] 시간 복잡도(time complexity)

시간 복잡도 계산 1

알고리즘	실행횟수
float Sum(float sumNum[], int n) {      float s = 0.0;      for(int i = 0; i < n; I++)           s += sumNum[i];      return s; }	-            -            1            n            n            1            -

명령어 총 실행횟수 = 2n + 2, 시간 복잡도 = O(n)

시간 복잡도 계산 2

알고리즘	실행횟수
float Sum(float a[], int n) {      if(n <= 0)           return (0.0);      else           return (Sum(a, n-1) + a[n]); }	- - 1 1 - 1 + T(Sum(n-1)) -

명령어 총 실행횟수 = 2n + 1, 시간 복잡도 = O(n)

  위의 알고리즘에서 사용된 순환식을 이용하면 명령어의 실행횟수는 다음과 같음을 알 수 있다.

T(Sum(n)) = 2               ,if n = 0

           = 2 + T(Sum(n-1) ,if n > 0

순환관계로부터 총 명령어 실행횟수를 구하는 방법은 다음과 같다.

T(Sum(n))  = 2 + T(Sum(n-1))
           = 2 + ( 2 + T(Sum((n-2)) )
           = 2 + ( 2 + ( 2 + T(Sum((n-3)) ) )
           ......
           = 2×n + T(Sum(0))
           = 2n + 2

따라서, 명령어 실행횟수의 총 합은 2n+2이고 시간 복잡도는 O(n)이다.