알고리즘 | 계산 복잡도, Big-O 표기법

프로그램의 효율성

프로그램의 효율성은 해당 프로그램이 얼마나 빠르게 원하는 결과를 도출하고, 그 과정에서 얼마나 적은 자원을 사용하는지를 기준으로 평가된다. 특히 알고리즘 코드를 작성하는 입장에서는, 내 코드 혹은 동료의 코드의 효율성을 빠르게 판단할 수 있는 인지적 도구가 필요하다. 

 

따라서 프로그램 효율성울 평가하는 두 가지 핵심 요소, 즉 1) 얼마나 빠른 시간 내에, 2) 얼마나 적은 자원을 사용하여 구현되었는지를 쉽게 파악할 수 있도록 1) '시간 복잡도(Time Complexity)'와 2) '공간 복잡도(Space Complexity)', 그리고 이들을 나타내는 표기법인 'Big-O' 개념을 배울 필요가 있다. 

 

백준 문제를 풀 때, 항상 문제에 시간 제한과 메모리 제한이 걸려 있다. 

여기서 '시간 복잡도'는 시간 제한에, '공간 복잡도'는 메모리 제한에 걸리지 않도록 돕는 보조적인 지식이다. 

만일 코딩테스트가 목적이라면, 일반적으로는 시간 제한이 문제가 되므로 시간 복잡도 개념을 잘 익혀둘 필요가 있다. 

 

 

빅-오 표기법 (Big-O Notation)

Big-O는 시간 복잡도와 공간 복잡도를 나타낼 때 주로 사용하는 표기법 중 하나이다. 이 표기법은 위에서 설명한 알고리즘의 효율성을 대략적으로, 그러나 핵심적인 측면에서 평가할 수 있게 돕는다.

 

특정 알고리즘에서 입력 개수(n)를 x축으로, 해당 입력 크기에 따른 실행 시간 혹은 필요한 공간을 y축으로 둔 함수의 최악의 성능 경계를 나타낸다. 여기서 O는 “on the order of”의 약자로, 쉽게 생각하면 “~만큼의 정도로 커지는” 이라고 해석할 수 있다. 

 

 

예를 들어, 배열의 모든 요소를 하나씩 순차적으로 탐색하는 알고리즘은 O(n)의 시간 복잡도를 가진다. 입력 크기가 n개일 때 n번의 연산이 필요하기 때문이다. 그러나, 배열의 특정 인덱스에 직접 접근하여 값을 얻는 연산은 O(1)의 시간 복잡도를 지닌다. 이는 배열의 접근이 인덱스를 기반으로 일어나며, 입력 크기와 상관없이 상수 시간이 소요되기 때문이다.

 

만일 상황에 따라 시간 복잡도의 범위가 다양하게 나올 수 있는 경우, Big-O 표기법은 알고리즘의 성능을 최악의 경우로 평가한다.

또한 Big-O 표기법은 알고리즘의 실제 실행 시간을 정확하게 예측하는 것이 아니라, 입력 크기가 커질 때 알고리즘의 성능이 어떻게 변화하는지의 경향만을 나타낸다. 

 

복잡도	설명	예시 알고리즘 (기준: 시간 복잡도)
O(1) (상수형 Big-O)	- 데이터 수에 상관없이 '연산 횟수가 고정'인 유형. - 데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않는다.	배열에 대한 인덱스 접근, 해시 테이블에 대한 연산
O(logn) (로그형 Big-O)	- '데이터 수의 증가율'에 비하여 '연산횟수의 증가율'이 훨씬 낮은 알고리즘. - ex) 데이터가 10배가 되면, 처리 시간은 2배가 된다.	이분 탐색
O(n) (선형 Big-O)	- 데이터 수와 연산횟수가 비례하는 알고리즘.	배열 순회, 단순 탐색
O(n*logn) (선형 로그형 Big-O)	- 데이터의 수가 2배로 늘 때, 연산횟수는 2배 조금 넘게 증가하는 알고리즘.	퀵 정렬, 병합(merge) 정렬
O(n^2) (제곱형 Big-O)	- 2중 for 반복문을 사용하여 모든 데이터 쌍을 비교하는 알고리즘.	버블 정렬, 선택 정렬, 삽입 정렬
O(n^3) (세제곱형 Big-O)	- 3중 for 반복문을 사용하는 알고리즘 또는 행렬 곱셈의 일반적인 알고리즘. - 행렬 곱셈의 일반적인 알고리즘은 O(n^3) 복잡도를 가진다. - 3중 이상의 for 반복문을 사용하는 알고리즘은 실무에서 거의 쓰이지 않는다. 실행시간이 비정상적으로 길어질 가능성이 높기 때문이다.	기본 행렬 곱셈 알고리즘
O(2^n) (지수형 Big-O)	- '지수적 증가'는 무서운 연산 횟수의 증가를 보이기 때문에 다른 방안을 찾아야 한다.	피보나치 수열의 단순 재귀 구현 등

 

Big-O로 시간 복잡도 파악하기

예시1: 선형 검색

def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
            
    return -1

위 코드는 arr 리스트에 x 값이 있으면 그 인덱스를 반환하고, 없으면 -1 을 반환한다.

최악의 경우 모든 원소를 검색해야 하므로 시간 복잡도는 O(n)이다.

 

 

예시2: 이분 탐색

이분 탐색은 정렬된 리스트에서 특정한 값을 빠르게 찾기 위한 알고리즘이다.

def binary_search(arr, x):
    low, high = 0, len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        
        if arr[mid] == x:
            return mid
        
        elif arr[mid] < x:
            low = mid + 1
            
        else:
            high = mid - 1
            
    return -1

 

처음에는 리스트의 중간 값을 선택한다. 이 선택된 중간 값과 찾고자 하는 값이 일치하는지 확인하며, 일치하지 않을 경우 중간 값이 찾고자 하는 값보다 큰지 작은지를 판단한다. 이 판단을 통해 다음 탐색할 범위를 절반으로 줄인다.

매 단계에서 탐색 범위를 절반으로 줄이므로, 시간 복잡도는 O(log n)이다.

 

---

Q. 잠깐, O(log n)이 아니라 로그의 밑이 2여야 맞는 거 아님?

A. 원래는 매번 탐색 범위가 절반으로 줄어드므로 밑이 2인게 맞다. 하지만 컴퓨터 과학에서는 통상적으로 밑을 생략하고 O(log n)으로 표기한다. 앞서 Big-O 표기법은 성능을 정확히 측정하기 위함이 아니라, 경향을 파악하기 위한 목적임을 알아본 바 있다. 때문에 비교적 작은 부분은 버리고 표기하는 것이다. 

 

또한, 실제로 로그의 밑이 바뀐다고 해서 실제 성능과 큰 괴리가 발생하지도 않는다. 밑이 10이든 2이든 성능은 상수 배 정도의 차이밖에 나지 않기 때문이다 (로그의 밑 변환 성질). 

 

chatGPT

---

 

시간 복잡도를 문제 풀이에 얼마나 활용할 수 있을까 

출처: https://www.acmicpc.net/board/view/35079

 

만약 특정 알고리즘 문제에 대한 코드를 작성했는데 O(n^2)의 시간 복잡도를 갖는다고 가정하자. 입력 크기가 10,000이라면 최악의 경우 시간 복잡도에 따른 연산의 횟수는 10,000의 제곱값인 1억이 된다. 그렇다고 해서 이 연산이 반드시 n초 내에 처리된다고 가정하는 것은 위험하다.

 

실제 실행 시간은 해당 시간 복잡도 외에도 각 입력값의 특성, 코드의 최적화 정도, 사용하는 언어와 그 언어의 라이브러리의 효율성, 컴퓨터의 성능 등 다양한 요소에 따라 달라진다. 따라서 시간 복잡도만으로 실제 실행 시간을 정확히 예측하는 것은 어렵고, 여러번의 테스트와 경험을 통해 더 정확한 예측을 할 수 있게 된다. 결국 경험치가 필요한 영역인 것 같긴 하다.

 

그러나 내 접근이 크게 어긋나고 있지는 않는지, 어느정도의 효율성을 가지는지에 대한 대략적인 가이드라인을 제시해줄 수 있다는 측면에서 시간 복잡도 개념은 유용하다고 볼 수 있다. 

 

 

Big-O로 공간 복잡도 파악하기

공간 복잡도는 알고리즘이 실행될 때 사용하는 메모리 양을 나타내므로, 알고리즘 문제를 풀 때 발생하는 메모리 문제와 관련이 있다. 주로 변수 할당, 데이터 구조의 크기 및 함수 호출 스택의 크기를 고려하여 계산된다.

 

예시1: 버블 정렬

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

버블 정렬은 기본적으로 주어진 배열 내에서 정렬을 수행하므로 추가적인 공간이 필요하지 않다.

이 경우 공간 복잡도는 O(1)이다.

 

예시2: 팩토리얼 (재귀 함수)

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n-1)

함수가 재귀적으로 호출되면 호출 스택에 함수의 상태가 저장된다. 따라서 깊이가 n인 재귀 호출에 대해 스택에 n개의 함수 호출 상태가 저장된다. 이 경우 공간 복잡도는 O(n)이다.

 

 

공간 복잡도를 문제 풀이에 얼마나 활용할 수 있을까 

 

big-O로 파악할 수 있는 공간 복잡도는 시간 복잡도에 비해서 제공하는 정보가 제한적이기에 직접적인 활용도는 낮다고 판단된다. (big-O 표기법으로 나타낼 수 없는 변수가 많음)

 

다만 공간 복잡도와 함께 수반되는 지식을 고려하면 메모리 초과가 발생할 경우 코드를 개선하는데 있어서 유용할 것 같다.

- 변수: 알고리즘이 실행되는 동안 사용되는 모든 변수의 메모리를 고려해볼 것 

- 데이터 구조: 리스트, 딕셔너리, 세트, 그래프, 트리 등의 데이터 구조가 사용될 때 해당 구조가 차지하는 메모리를 고려해볼 것 

- 함수 호출 스택: 함수가 호출될 때 해당 호출에 대한 정보가 저장되는 메모리를 고려해볼 것

 

 

알고리즘 풀이에서 발생하는 대표적인 메모리 문제

 

알고리즘 문제를 풀 때 발생하는 대표적인 메모리 문제와 그 해결법을 알아보는 것이 더 유용할 수도 있을 것 같다. 

끝으로 해당 내용만 알아보고 이번 공부는 마치도록 하자! 

 

1. 재귀를 사용하는 알고리즘

• 문제: 재귀를 사용하는 알고리즘은 호출 스택을 사용하므로, 깊은 재귀 호출이 발생하면 스택 오버플로우가 발생할 수 있다.
• 해결법: 깊은 재귀 호출 대신 반복문 또는 메모이제이션을 사용하여 재귀의 깊이를 줄일 수 있다. 또한 꼬리 재귀 최적화(Tail Recursion Optimization)를 지원하는 언어에서는 꼬리 재귀를 사용하여 스택 오버플로우 문제를 완화할 수 있다고 한다. 

2. 대량의 데이터 저장

• 문제: 많은 양의 데이터를 배열, 리스트, 해시맵 등의 자료구조에 저장해야 하는 경우, 사용 가능한 메모리 한계를 초과할 수 있다.
• 해결법: 필요하지 않은 데이터는 메모리에서 제거하거나, 분산 저장 시스템이나 데이터베이스 등 외부 저장소를 활용하여 데이터를 저장할 수 있다. 또한, 압축 알고리즘을 사용하여 데이터의 크기를 줄일 수도 있다.

3. 동적 프로그래밍

• 문제: 동적 프로그래밍은 큰 문제를 작은 부분 문제로 분해하여 풀이하는 방식이다. 각 부분 문제의 결과를 저장하기 위해 추가적인 메모리를 사용한다고 한다. 이때, 메모리 사용이 늘어나면서 공간 복잡도가 증가할 수 있다. 
• 해결법: 'State Compression' 기법을 사용하여 필요한 부분 문제의 결과만을 저장할 수 있다고 한다. 예를 들어, 피보나치 수열에서는 이전 두 수만을 저장하여 현재 수를 계산할 수 있으므로 O(1)의 공간만 사용할 수 있다.