시간 복잡도

알고리즘의 효율성

 

알고리즘을 평가할 때 가장 중요한 기준 중 하나는 바로 '효율성'이다. 알고리즘의 효율성은 크게 시간 복잡도와 공간 복잡도로 나누어 평가할 수 있다. 이 두 가지 복잡도는 알고리즘의 성능을 결정짓는 핵심 요소로, 알고리즘을 설계하고 최적화하는 데 있어 중요한 역할을 한다. 시간 복잡도는 알고리즘을 실행하는 데 필요한 시간을, 공간 복잡도는 알고리즘을 실행하는 데 필요한 메모리 공간을 의미한다. 이 두 가지 복잡도를 이해하고 최적화하는 것은 효율적인 알고리즘을 설계하는 데 필수적이다.

시간 복잡도 (Time Complexity)

 

시간 복잡도란 알고리즘의 효율성을 판단하기 위한 지표로서, 알고리즘의 절대적인 실행 시간이 아닌, 알고리즘을 수행하는데 사용되는 연산들이 몇 번 이루어지는가에 대한 것을 수로 표기한 것이다. 여기서 연산은 산술, 대입, 비교, 이동을 말한다. 시간 복잡도 성능 측정에 사용되는 표기법은 크게 세 가지로 나뉘며, Big-O, Big-Omega( Ω ), Big-Theta( θ )가 있다.

• Big-Omega( Ω ) : 최선(Best Case)의 경우
• Big-Theta( θ ) : 평균(Average Case)의 경우
• Big-O : 최악(Worst Case)의 경우

알고리즘 성능 평가시에는 데이터가 최악으로 주어졌을때도 처리가 가능한지를 판단해야 하므로 빅-오 표기법이 가장 중요하다.

Big-O 표기법

시간 복잡도 함수의 그래프

 

<Better>   O(1) < O(logn) < O(n) < O(n × logn) < O(n^2) < O(2^n) O(n!)   <Worse>

O(1)

상수 시간(Constant Time) : 입력값(n)의 크기 증가와 관계 없이 실행 시간이 동일하다.

• 입력값(n)의 크기와 관계 없이 동일한 수의 스텝이 필요하다.
• 문제를 해결하는데 오직 한 단계만 처리함.

def Constant_Time(lst):
    print(lst[0])

O(logn)

로그 시간(Logarithmic Time) : 입력값(n)의 크기가 증가함에 따라 매 실행 시간이 1/2 줄어든다.

• 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.

이진 검색 알고리즘(Binary Search)이 O(logn)의 시간 복잡도를 가진다.

• 이진 검색 알고리즘에서는 원하는 값을 탐색할 때, 매 스텝마다 절반의 아이템을 없앤다. 
• 따라서 입력값이 2배가 되어도 작업을 수행하는 데 필요한 스텝은 1씩만 증가한다.

def log_time(lst, target):
    low = 0
    high = len(lst)-1
    
    while low <= high:
    	mid = (low + high) // 2
        if lst[mid] == target:   # 타겟이 정중앙에 위치
            return mid
        elif lst[mid] < target:  # 타겟이 중간보다 오른쪽에 있음 (왼쪽 절반을 버림)
            low = mid + 1
        else:                    # 타겟이 중간보다 왼쪽에 있음 (오른쪽 절반을 버림)
            high = mid - 1
    
    return False

O(n)

선형 시간(Linear Time) : 입력값(n)의 크기가 증가함에 따라 실행 시간 또한 같은 비율로 증가한다.

• 입력값이 증가함에 따라 스텝의 수도 비례해서 증가한다.
• 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.

def Linear_time(lst):
    for item in lst
    	print(item)

O(nlogn)

선형 로그 시간(Linearithmic Time) : 입력값(n)의 크기가 증가함에 따라 실행 시간이 nlogn 만큼 증가한다.

• 데이터를 반으로 나누어 각각 정렬하고 합치는 정렬 알고리즘에서 주로 사용된다.
• 문제를 해결하기 위한 단계의 수가 (n × logn)번 만큼의 수행시간을 가진다.

O(nlogn)의 시간 복잡도를 가지는 알고리즘

• 병합 정렬 (Merge Sort)
• 힙 정렬 (Heap Sort)
• 퀵 정렬 (Quick Sort)

def n_logn(n):
    for i in range(n):                # 바깥 루프는 n번 반복
    	j = 1
        while j < n:                  # 안쪽 루프는 2배씩 커지면서 실행횟수가 logn이 됨.
            print(f'i: {i}, j: {j}')
            j = j * 2

O(n^2)

이차 시간(Quadratic Time

) : 입력값(n)의 크기가 증가함에 따라 실행 시간이 제곱만큼 증가한다.

• 중첩 반복문에서 발생하며, 입력값의 제곱만큼의 스텝이 필요하다.
• 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.

O(n^2)의 시간 복잡도를 가지는 알고리즘

• 선택 정렬 (Selection Sort)
• 버블 정렬 (Bubble Sort)
• 삽입 정렬 (Insertion Sort)

def Quadratic_time(lst):
    for i in lst:
    	for j in lst:
        	print(f'({i}, {j})')
        print()

반복문의 개수와 시간 복잡도의 관계

 

반복문이 단순히 여러개 있는것과, 서로 겹쳐져 있는지에 따라 시간 복잡도가 달라지게 된다.

 

1. 독립적인 루프 → O(n)

 

for i in range(n):
    pass
for j in range(n):
    pass

 

반복문이 중첩되지 않고 단순히 여러개 있다면 계산은 단순히 n번만 이루어 지므로 시간 복잡도는 O(n)이 된다.

 

2. 중첩 반복문 → O(n^2)

for i in range(n):
    for j in range(n):
    	pass

 

반복문 안에 또 반복문이 들어간 중첩구조이다. 이러면 계산이 n^2번 이루어 지므로 시간 복잡도는 O(n^2)이 된다.

 

3. 변수가 2배씩 증가 / 감소하는 반복문 → O(logn)

i = 1
while i < n:
    i = i * 2   # or i = i // 2

 

변수가 1씩 커지는게 아니라 매번 2배 혹은 절반으로 줄어드는 구조. 시간 복잡도는 O(logn)이 된다.

 

4. 위의 상황의 중첩 반복문 → O(nlogn)

for i in range(n):
    j = 1
    while j < n:
    	j = j * 2    # or j = j // 2

 

내부 루프는 실행 횟수가 logn이 되고 외부 루프는 실행 회수가 n이 되므로 시작 복잡도는 O(nlogn)이 된다.

리스트(List)의 주요 함수들의 시간 복잡도

함수	시간 복잡도	설명
append()	O(1)	리스트의 맨 뒤에 원소만 추가하므로 데이터를 옮길 필요가 없다.
insert()	O(n)	특정 인덱스에 원소를 삽입하게되면 모든 데이터를 뒤로 밀어내야 하므로 데이터의 개수(n)에 비례해서 시간이 걸린다.
pop()	O(1)	리스트의 맨 뒤 요소만 꺼내서 삭제하면 되므로 데이터 이동이 없음.
remove()	O(n)	리스트에서 첫 번째부터 타겟값을 찾기위해 O(n) 시간 복잡도가 생기므로 결국 O(n)
sort()	O(nlogn)	파이썬은 Timsort라는 정렬 알고리즘을 사용하므로 최악의 상황에도 O(nlogn)보장
len()	O(1)	리스트를 만들 때 내부적으로 원소의 개수를 저장해두므로 데이터가 많아도 O(1)
extend()	O(n)	추가되는 새로운 데이터 개수에 비례하므로 시간 복잡도는 O(n)
index()	O(n)	리스트의 맨 앞부터 타겟값이 나올 때까지 하나씩 선형 탐색 해야 하므로 최악의 경우 O(n)
reverse()	O(n)	리스트의 순서를 거꾸로 뒤집어야 하므로 데이터의 개수 n에 비례해서 시간 복잡도도 O(n)
sorted()	O(nlogn)	sort와 동일한 알고리즘을 사용하므로 O(nlogn)
count()	O(n)	처음부터 끝까지 모든 원소를 전부 확인해야 하므로 O(n)소요.

비효율적인 코드와 효율적인 코드

def inefficient(n):
    total = 0
    
    for i in range(1, n+1):  # for문을 활용해 1부터 n까지 하나씩 더해나간다.
    	total += i
    return total
    
print(inefficient(10))
# 55

 

테스트처럼 n=10이라고 하면 반복문이 10회 반복된다. 입력 데이터 크기 n에 비례해서 연산 횟수가 늘어나기 때문에 이 코드의 시간 복잡도는 O(n)이라고 할 수 있다.

def efficient(n):
    return n * (n + 1) // 2  # for문 대신 공식으로 한번에 계산
    
print(efficient(10))
# 55

 

이렇게 코드를 구성한다면 n의 값과는 상관없이 사칙연산만 하고 결과를 알 수 있기 때문에, 데이터 크기와 상관없이 실행 속도가 일정한 시간 복잡도인 O(1)이 된다.

 

알고리즘을 잘 짠다는 것은 그냥 단순히 작동이 잘 되는 코드를 짠다는걸 넘어서 얼마나 효율적인 코드를 작성하는지를 의미한다. 반복문을 여러번 쓰더라도 기능만 작동하면 되겠지 라고 생각했었지만, 자료 조사를 하면서 반복문은 줄이되, 코드의 기능은 동일하게 코드를 구성해야 겠다는걸 깨닫게 되었다.