이중 for문의 시간복잡도

예제를 통해 이중 for문의 시간복잡도를 구해보자

algorithm sum(A, n):
  sum = 0			# 1번
  for i=0 to n-1 do		# n번
    for j=i to n-1 do		# 아래에서 설명
      sum += A[i] * A[j]	# 3번
  return sum

각 for문의 돌아간 횟수

i	j
0	n
1	n-1
2	n-2
...	...
n-1	n-(n-1)=1

식으로 나타내기

for j=i to n-1 do
# 여기서 i가 n-1이라면 j=도 n-1이 되고 to n-1 즉, n-1이 n-1이 될 때 까지니까 한 번 돌게 된다.
# 규칙을 부여해서 찾는다면 n-(i의 시작 수)가 되니 n-(n-1)이 되어 n-n+1 즉, 1이 되는 방법도 있다.

결국 이중 for문의 횟수는 위 표의 j 밑에 있는 값들을 모두 더한게 된다.

거꾸로 1부터 ... n-2 + n-1 + n 이 되니 결국

= 1+2+...+n 이 되는거나 마찬가지

 

여기서 1부터 n까지의 합에 대한 공식을 적용하면 다음과 같다.

n(n+1) / 2

 

정리

결과적으로 시간복잡도는 T(n) = 3n²/2 + 3n/2 + 1이 된다.