시간복잡도

알고리즘 문제 풀기 : Step1) 문제 이해하기, Step2) 접근 방법, Step3) 코드 설계, Step4) 코드 구현

1. 시간복잡도

• 시간복잡도에 데이터의 크기(n)를 넣어서 나온 값이 100,000,000(10^8)이 넘게 되면, 코딩테스트에서 시간 초과할 가능성이 있다.
• 그러므로, 관행적으로 10^8을 넘지 않도록 유의한다.

2. 제약조건

• 한 문제의 다양한 제약조건 중 시간이 증가할만한 것을 N의 기준으로 삼는다.

3. Big-O Notation

• T(n) = n^2 + 2n + 1에서 +1과 2n은 무시될 수 있다.
  • 1 무시 이유 : n의 변화에 따른 T(n)의 변화 정도 판단이 목적
  • 2n 무시 이유 : n이 증가할 수록 2n의 비율이 미미해진다.
  • 따라서 T(n) = n^2 + 2n + 1에서 Big-O -> O(n^2)

T(n)에서 실제로 영향력을 끼치는 부분을 Big-O라고 함

• T(n) = n^2 + 2n + 9 -> O(n^2)
• T(n) = n^4 + n^3 + n^2 + 1 -> O(n^4)
• T(n) = 5n^3 + 3n^2 + 2n + 1 -> O(n^3)

O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!)

4. 예시

• O(1) : 입력 데이터에 의존하지 않는 경우

if a > b:
	return True
else:
	return False

• O(log n) : 각 단계에서 입력 데이터의 크기를 줄여나갈 때

def binary_search(data, value):
    n = len(data)
    left = 0
    right = n - 1
    while left <= right:
        middle = (left + right) // 2
        if value < data[middle]:
            right = middle - 1
        elif value > data[middle]:
            left = middle + 1
        else:
            return middle
    raise ValueError('Value is not in the list')
    
if __name__ == '__main__':
    data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    print(binary_search(data, 8))

• O(n) : 입력 데이터의 크기에 따라 실행 시간이 선형적으로 증가할 때

def linear_search(data, value):
    for index in range(len(data)):
        if value == data[index]:
            return index
    raise ValueError('Value not found in the list')
    
if __name__ == '__main__':
    data = [1, 2, 9, 8, 3, 4, 7, 6, 5]
    print(linear_search(data, 7))

• O(nlog n) : 입력 데이터의 각 연산이 로그 시간 복잡도를 갖는 경우

def merge_sort(data):
    if len(data) <= 1:
        return
    
    mid = len(data) // 2
    left_data = data[:mid]
    right_data = data[mid:]
    
    merge_sort(left_data)
    merge_sort(right_data)
    
    left_index = 0
    right_index = 0
    data_index = 0
    
    while left_index < len(left_data) and right_index < len(right_data):
        if left_data[left_index] < right_data[right_index]:
            data[data_index] = left_data[left_index]
            left_index += 1
        else:
            data[data_index] = right_data[right_index]
            right_index += 1
        data_index += 1
    
    if left_index < len(left_data):
        del data[data_index:]
        data += left_data[left_index:]
    elif right_index < len(right_data):
        del data[data_index:]
        data += right_data[right_index:]
    
if __name__ == '__main__':
    data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]
    merge_sort(data)
    print(data)

• O(n^2) : 입력 데이터의 각 값에 대해 선형 시간 연산을 수행해야 하는 경우

def bubble_sort(data):
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(data)-1):
            if data[i] > data[i+1]:
                data[i], data[i+1] = data[i+1], data[i]
                swapped = True
    
if __name__ == '__main__':
    data = [9, 1, 7, 6, 2, 8, 5, 3, 4, 0]
    bubble_sort(data)
    print(data)

• O(2^n) : 입력 데이터가 추가될 때마다 증가율이 두 배가 되는 경우

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

• O(n!) : 입력 데이터의 크기에 따라 계승적 방식으로 증가할 때

def heap_permutation(data, n):
    if n == 1:
        print(data)
        return
    
    for i in range(n):
        heap_permutation(data, n - 1)
        if n % 2 == 0:
            data[i], data[n-1] = data[n-1], data[i]
        else:
            data[0], data[n-1] = data[n-1], data[0]
    
if __name__ == '__main__':
    data = [1, 2, 3]
    heap_permutation(data, len(data))