알고리즘 시간복잡도2

해당 자료는 유튜브 신찬수 한국외대 교수님 강의를 시청하며 작성되어 있습니다. 🙏🏻

알고리즘 시간 복잡도(time complexity)

알고리즘 시간 복잡도를 계산하는 방법

1. 모든 입력에 대해 기본연산 횟수를 더한 후 평균(현실적으로 불가능)
2. 가장 안 좋은 입력(Worstcase input)에 대한 기본 연산 횟수를 측정(worstcase time complexity)

2번의 방법 경우 어떤 입력에서도 W.T.C보다 수행시간이 크지 않다. 즉 연산 횟수가 보장된다!

알고리즘 수행 시간 복잡도를 정의하는 방법

알고리즘 수행 시간 = 최악의 입력에 대한 기본 연산 횟수

예시

input: n개의 정수를 갖는 배열 A
output: A의 수 중에서 최대값 리턴

alogirithm arrayMax(A, n):
  currentMax = A[0]
  
  for i = 1 to n-1 do
    if currentMax < A[i]:
      currentMax = A[i]
  return currentMax

위 코드에서 currentMax < A[i] 조건이 항상 참일 경우 가장 연산횟수가 크다.

예시: A = [2, 5, 7, 9, 15, 26]

for문이 n - 1만큼 실행할 때 기본연산은 2번 수행씩 된다. (if 참인지 비교, 참일경우 하위 코드 실행)

대입연산: 1 단위시간
반복문: (n - 1) * 2 = 2n - 2 단위시간

즉, T(n) = 2n - 1

n = 6 일때, T(6) = 12 - 1 = 11

시간 복잡도 예시 1

algorithm sum1(A, n):
  sum = 0                  # 대입연산 (1 단위시간)
  for i = 0 to n - 1 do
    if A[i] % 2 == 0:    # 나누고, == 맞는지 확인(2 단위시간)
      sum += A[i]        # 더하고 대입하라(2 단위시간)
  return sum

A: 모든 값이 짝수인 경우 W.C 입력인 것

T(n) = 4n + 1

=> for 문이 n번 돌고, if 2번, 참일 경우 2번 즉 4번, 첫번째 대입 해서 1번!

시간 복잡도 예시 2

algorithm sum2(A, n)
  sum = 0                 # 대입 연산(1 단위시간)
  for i = 0 to n - 1 do   
    for j = i to n - 1 do  
      sum += A[i] * A[j] # 더하고 대입(2 단위), 곱하기(1 단위)
  return sum

두번째 for문에 대해 j가 1+2+3+...+n 번인 것임므로 n(n+1)/2

=> for문이 n번 돌고, 그 하위 for문은 n(n+1)/2, if 부분은 3번,
즉 n(n+1) / 2 3 n, 첫번째 대입 해서 1번!

T(n) = ((3/2)n)(n+1) + 1
= (3/2)n^2 - (3/2)n + 1