시간복잡도(Big-O)

Nicholas·2022년 7월 29일
0

Algorithm & DataStructure

목록 보기
12/12

시간복잡도

  • 알고리즘의 성능 비교

시간복잡도를 해야하는 이유

  • 알고리즘의 성능은 코드의 종류에 따라, 컴퓨터의 사양에 따라 변한다.
  • 이러한 변동을 동일하게 하기위해 “가상컴퓨터+가상언어+가상코드” 위에서 작업한다.
  • 가상컴퓨터는 폰노이만이 정립한 RAM(Random Access Machine)위에서 동작한다
  • RAM은 “CPU + Memory + 기본연산” 으로 이루어져있다.

기본연산

  • 단위시간에 수행되는 연산
    1. 배정,대입,복사 연산 : A=B
    2. 산술연산 : +,-,*,/
    3. 비교연산 : >, <, =>, =<, ==, !=
    4. 논리연산 : and, or, not
    5. 비트연산 : bit-and, or ,not
    이러한 RAM모델 위에서 알고리즘의 시간을 측정하여 비교해야 한다.

가상언어(Pseudo Language)

  • 배정, 산술, 비교 논리, 비트 연산이 가능한 언어
  • 분기문 가능 : if, if else, 등
  • 반복문 가능 : for, while 등
  • 함수 정의, 호출, 반환 가능
  • 가상언어는 정해진것이 아닌 위에것에 만족하는 언어는 다 가능
    (Python, C, JS, Java, Ruby 등)

가상코드(pseudo code)

  • 추상화된 로직구조(함수)
  • input 과 output구조

알고리즘의 시간복잡도의 정의

시간복잡도 구하는 방법

  1. 모든 입력에 대해서 기본연산 횟수를 더한 후 평균 : 가장 정확하지만 현실적으로 불가능, 조건이 너무 많음
  2. 가장 안좋은 입력(기본연산이 최대로 한 입력값)에 대한 기본 연산 횟수를 측정 (W.T.C : Worstcase Time Complexity)
    1. 장점 : 어떤 입력에 대해서도 W.T.C 보다 수행시간이 크지 않다.
    2. 단점 : 정확성이 떨어질수 있다.

    ⇒ 알고리즘의 수행시간은 최악의 입력에 대한 기본 횟수로 정의한다.

Big-O 표기법

# A = [_,_,_,] list size = n
# W.T.C = A의 모든값이 짝수인 경우

def algorithnm1_arrayMax(A,n):
    currentMax = A[0]
    for i in range(0, n-1):
        if currentMax < A[i]:
            currentMax = A[i]
    return currentMax

# 최종 연산횟수 T(n) = 2n-1

def algorithnm3_sum1(A,n):
    sum = 0                   # 연산 1회(대입연산)
    for i in range(0, n-1):   # 연산 n번(반복연산)
        if A[i] / 2 == 0:     # 연산 2회 (산술연산, 비교연산)
            sum += A[i]       # 연산 2회 (산술연산, 대입연산)
    return sum                # n x 4 연산

# 최종 W.T.C 연산횟수 T(n) = 4n+1

def algorithnm3_sum2(A,n):
    sum = 0                      # 연산 1회(대입연산)
    for i in range(0, n-1):      # 연산 n번(반복연산)
        for j in range(i, n-1):  # 연산 n-1번(반복연산)
            sum += A[i]*A[j]     # 연산 n(n-1)의 2분의1 x 3
    return sum

# 최종 W.T.C 연산횟수 T(n) = (3분의2)n제곱 - (3분의2)n + 1

알고리즘의 수행시간 = 최악의 경우의 입력에 대한 기본연산 횟수 =
W.T.C(Worstcase Time Complexity)

algorithnm1(arrayMax) : T1(n)T_1(n) = 2n-1
algorithnm2(sum1) : T2(n)T_2(n) = 4n+1
algorithnm3(sum2) : T3(n)T_3(n) = 32n232n+1\frac{3}{2}n^2-\frac{3}{2}n+1

1. algorithnm2가 algorithnm1보다 2배 느리다
2. algorithnm3는 $n<\frac{5}{3}$면 algorithnm2보다 빠르다
3. algorithnm3는 모든 n에 대해서 algorithnm1보다 느리다
4. algorithnm3은  $n>\frac{5}{3}$면 항상 algorithnm2보다 느리다.
5.  $T_1(n)$ 과  $T_2(n)$는 선형적으로 정비례하게 증가하고  $T_3(n)$은 제곱으로 증가한다. 증가율은 최고차n의 최고차항이 된다.

Big-O의 표기법이란? 함수값을 결정하는 최고차항으로 만 간단하게 표기하는 방법

T1(n)T_1(n) = 2n-1 ⇒ O(n)

T2(n)T_2(n) = 4n+1 ⇒ O(n)

T3(n)T_3(n) = 32n232n+1\frac{3}{2}n^2-\frac{3}{2}n+1 ⇒ O(n2n^2)

  1. 최고차항만 남긴다
  2. 최고차항 계수(상수)는 생략
  3. Big-O(최고차항)

Big-O의 다른 예

def incrument_one(a):
    return a+1          # 연산 1회(산술연산)

def number_bit(n):
    count = 0           # 연산 1회(대입연산)
    while n > 0:        # 연산 log2의 n회(반복연산)
        n = n //2       # 연산 2(산술연산, 대입연산)
        count +=1       # 연산 2회(산술연산, 대입연산)
    return count

increment_one : T4(n)T_4(n) = O(1)

number_bit :
T5(n)T_5(n) = 4log2n+n4{log_2}^n+n=O(log2n)O({log_2^n})(n2count=1\frac{n}{2^{count}} = 1n=2countn = 2^{count}count=log2ncount = {log_2}^n )

profile
WEB Developer

0개의 댓글