알고리즘의 효율성, 분석과 차수 - 시간복잡도, 빅오 표기법

권한·2026년 3월 3일

알고리즘/자료구조

목록 보기

5/7

알고리즘

어떤 문제를 컴퓨터로 풀기 위한 효율적 절차. 풀이의 단계별 절차를 명확하게 기술

순차 탐색

문제 : 어떤 수 x가 n개의 수로 구성된 리스트 s에 존재하는가?

해답 : x가 존재하면 x의 인덱스, 존재하지 않으면 0

파라미터 : 정수n(>0), 리스트S, 원소x

입력사례 : S = [0, 10, 7, 11, 5, 13, 8], n = 6, x = 5

입력사례에 대한 해답 : location = 3

알고리즘 : 모든 S에 대해 x의 인덱스를 찾아주는 단계별 절차

S의 첫째 원소에서 시작해 x를 찾을 때까지 각 원소를 차례대로 x와 비교(없다면 끝까지 비교)

x를 찾으면 x의 인덱스 리턴, 찾지 못했다면 0리턴
def seqsearch(n, S, x):
    loc = 1
    while loc <= n and S[loc] != x:
        loc += 1
    if loc > n:
        return 0
    return loc

S = [0, 10, 7, 11, 5, 13, 8]
x = 5
location = seqsearch(len(S) - 1, S, x)
print("location =", location)
=> n번 비교

알고리즘의 효율성

알고리즘의 성능 : 시간과 공간사용의 효율. 컴퓨터의 실행속도나 메모리의 가격에 무관
ex) 순차탐색(정렬되지 않은 경우) vs 이분검색(정렬된 경우)

이분 검색

리스트 s와 어떤수 x가 주어짐

x를 리스트 중앙의 원소와 비교. 같다면 알고리즘 종료

x가 그 원소보다 작으면 x는 왼쪽에 위치할 것. 왼쪽 리스트에 대해 이진탐색 시행
x가 그 원소보다 크면 x는 오른쪽에 위치할 것. 왼쪽 리스트에 대해 이진탐색 시행

더 이상 찾을 원소가 없으면 종료
def binsearch(n, S, x):
    low = 1
    high = n
    loc = 0
    while low <= high and loc == 0: #loc이 0이 아니라면 발견함
        mid = (low + high) // 2
        print(low, mid, high)
        if x == S[mid]:
            loc = mid
        elif x < S[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return loc

S = [-1, 5, 7, 8, 10, 11, 13] #-1은 쓰레기값. 인덱스가 1부터 시작하도록 설정
x = 2
location = binsearch(len(S) - 1, S, x)
print("S = ", S[1:])
print("x = ", x)
print("location = ", location)
=> logn + 1 (lgn + 1으로도 표기. 밑이 2인 로그)

재귀적 정의를 이용하는 것은 작성하기 쉽고 이해하기도 쉽지만 같은 계산을 여러번 하는 경우 비효율적이다. (이미 계산한 것을 계산)
=> 이미 계산된 것은 리스트에 저장해서 꺼내쓰면 됨

ex) 피보나치 수열 구현

# 재귀 함수를 사용한 피보나치
def fib(n):
    if n <= 1:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

for i in range(11):
    print(fib(i), end=' ')

# 중복 계산을 개선한 피보나치 
def fib(n):
    f = [0] * (n + 1) #리스트 컴프리헨션. 배열 초기화
    if n > 0:
        f[1] = 1
        for i in range(2, n + 1):
            f[i] = f[i - 1] + f[i - 2]
    return f[n]

for i in range(11):
    print(fib(i), end=' ')

💡 리스트f를 사용하지 않고 반복문으로 피보나치항 구하기

알고리즘의 분석

정확성 분석 : 모든 입력 사례에 대해 정확한 해답을 찾는다는 것을 증명
효율성 분석 : 입력 크기가 커지는 정도에 따른 성능의 변화량 증명
- 시간 복잡도 time complexity : 시간 기준 알고리즘 효율성 분석
- 공간 복잡도 space complexity : 공간 기준 알고리즘 효율성 분석 (빅데이터의 경우 상당한 신경이 필요)

알고리즘의 성능 분석

퍼포먼스 측정 : 실행 시간 직접 측정 or 실행 명령 숫자 세기 -> 컴퓨터 성능/언어 따라 달라짐

복잡도 분석 : 입력 크기에 따른 단위 연산 실행 횟수 세기 -> 컴퓨터나 언어와 무관

입력 크기 : 문제가 가진 파라미터(입력 사례의 크기. input size)

단위 연산 : 알고리즘 실행의 기본이 되는 명령어들의 집합(Basic Operation)

for문은 항상 n번 실행 : T(n) = n

def sum(S):
  n = len(S)
  res = 0
  for i in range(n):
      res += S[i] # 단위 연산. n번 반복하므로 f(n) = n
  return res

교환정렬 :

def exchange(S):
n = len(S)
for i in range(n - 1): #n - 1번 (0~n-2)
    for j in range(i + 1, n): #n, n-1, ... 2, 1 ->  
        if S[i] > S[j]: # 단위 연산. T(n) = (n - 1)n / 2
            # (swap은 무조건 하는 것이 아니므로 정확한 실행속도 알아내기 부적절)
            S[i], S[j] = S[j], S[i]

행렬곱셈 :

def matrixmult(n, A, B): #입력크기 n
C = [[0] * n for _ in range(n)]
for i in range(n): #n회
    for j in range(n): #n회
        for k in range(n): #n회
            C[i][j] += A[i][k] * B[k][j] #단위 연산. +보다는 *이 더 무거운 연산임

입력 사례에 따른 시간 복잡도 분석
- 일정 시간 복잡도 : 입력 사례에 따라 달라지지 않는 경우
- 최악worst-case, 최적best-case, 평균average-case 시간 복잡도 : 입력 사례에 따라 달라지는 경우
  
  순차탐색의 시간 복잡도 분석
  - 최악 : W(n) = n
  - 최적 : B(n) = 1
  - 평균 : x가 k번째에 있다면 k번 비교 \