알고리즘 평가법

📌 시간 복잡도

시간 복잡도(Time Complexity)는 인풋 크기에 비례하는 알고리즘의 실행 시간을 나타낸다.

시간 복잡도가 작은 알고리즘이 더 빠른 알고리즘이다.

• 거듭제곱 (Exponentiation)

• 로그 (Logarithms)
  

• 1부터 n까지의 합
  

1. 점근 표기법 (Big-O Notation)

점근 표기법의 핵심은 n이 크다고 가정하는 것이다. 따라서 상수항은 생략된다.⭐
n이 크지 않으면, 안 좋은 알고리즘을 쓰더라도 문제가 없다.

O(n^2)이라고 표기한다.

---

📌 탐색 알고리즘 평가하기

1. 선형 탐색

선형 탐색의 시간 복잡도는 O(1) + O(1) + O(n) + O(1) = O(n + 3) = O(n)이다.

2. 이진 탐색

이진 탐색의 시간 복잡도는 O(1) + O(1) + O(log n) + O(1) = O(log n + 3) = O(log n)이다.

---

📝 알고리즘 평가 주의 사항

• 인풋 크기와 상관 없이 실행되는 코드만 O(n)이다.
• sorted 함수나 sort 메소드를 사용하면 내부적으로 O(nlogn)의 정렬이 이루어진다.
• 리스트에서 in 키워드를 통해 값의 존재 여부를 확인하면 O(n)이다.

---

📝 주요 시간 복잡도 총 정리

1. O(1)
   인풋의 크기가 소요 시간에 영향이 없다는 뜻이다.

# O(1) 함수
def print_first(my_list):
    print(my_list[0]) 

print_first([2, 3])
print_first([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53])

반복문이 없으면 대체로 O(1)이다.

2. O(n)

# O(n) 함수
def print_each(my_list):
    for i in range(len(my_list)):
        print(my_list[i])

반복문이 있고, 반복되는 횟수가 인풋의 크기와 비례하면 일반적으로 O(n)이다.

# O(n) 함수
def print_half(my_list):
    for i in range(len(my_list) // 2):
        print(my_list[i])

n/2번 반복한다면 O(1/2n)이지만 상수항을 무시하므로 O(n)이다.

# O(n) 함수
def print_three_times(my_list):
    for i in range(len(my_list)):
        print(my_list[i])

    for i in range(len(my_list)):
        print(my_list[i])

    for i in range(len(my_list)):
        print(my_list[i])

반복문이 세 개이므로 O(3n)이지만 상수항을 무시하므로 O(n)이다.

3. O(n^2)
   반복문 안에 반복문이 있는 경우

# O(n^2) 함수
def print_pairs(my_list):
    for i in range(len(my_list)):
        for j in range(len(my_list)):
            print(my_list[i], my_list[j])

두 반복문 다 인풋 크기에 비례하므로 O(n^2)이다.

3. O(n^3)

# O(n^3) 함수
def print_triplets(my_list):
    for i in range(len(my_list)):
        for j in range(len(my_list)):
            for k in range(len(my_list)):
                print(my_list[i], my_list[j], my_list[k])

4. O(log n)

# O(lg n) 함수
# 2의 거듭제곱을 출력하는 함수
# (이번에는 인풋이 리스트가 아니라 그냥 정수입니다)
def print_powers_of_two(n):
    i = 1
    while i < n:
        print(i)
        i = i * 2

i가 두 배씩 증가한다.

# O(lg n) 함수
# 2의 거듭제곱을 출력하는 함수
# (이번에는 인풋이 리스트가 아니라 그냥 정수입니다)
def print_powers_of_two(n):
    i = n
    while i > 1:
        print(i)
        i = i / 2

5. O(n log n)

def print_powers_of_two_repeatedly(n):
    for i in range(n): # 반복횟수: n에 비례
        j = 1
        while j < n: # 반복횟수: lg n에 비례
            print(i, j)
            j = j * 2

def print_powers_of_two_repeatedly(n):
    i = 1
    while i < n: # 반복횟수: lg n에 비례
        for j in range(n): # 반복횟수: n에 비례
            print(i, j)
        i = i * 2

---

📌 공간 복잡도

공간 복잡도(Space Complexity)는 인풋 크기에 비례해서 알고리즘이 사용하는 메모리 공간을 나타낸다.

1. O(1)

def product(a, b, c):
    result = a * b * c
    return result

파라미터 a, b, c가 차지하는 공간을 제외하면 추가적으로 변수 result가 공간을 차지합니다. result가 차지하는 메모리 공간은 인풋과 무관하기 때문에 함수 product의 공간 복잡도는 O(1)이다.

2. O(n)

def get_every_other(my_list):
    every_other = my_list[::2]
    return every_other

파라미터 my_list가 차지하는 공간을 제외하면 추가적으로 변수 every_other가 공간을 차지한다.
리스트 every_other에는 my_list의 짝수 인덱스의 값들이 복사돼서 들어간다.

n/2개의 값이 들어가므로 O(n/2) = O(n)이다.

3. O(n^2)

def largest_product(my_list):
    products = []
    for a in my_list:
        for b in my_list:
            products.append(a * b)
    
    return max(products)

파라미터 my_list가 차지하는 공간을 제외하면 추가적으로 변수 products, a, b가 공간을 차지합니다. 우선 a와 b는 그냥 정수 값을 담기 때문에 O(1)이다.

리스트 products에는 my_list에서 가능한 모든 조합의 곱이 들어갑니다. 그렇다면 총 n^2개의 값이 들어가겠죠? 따라서 largest_product의 공간 복잡도는 O(n^2)이다.

---

📝 정리

• type 함수를 사용하면 파라미터의 데이터 타입이 리턴됩니다. 시간 복잡도는 O(1)이다.
• max,min 의 시간 복잡도는 O(n)입니다.
• 파라미터를 n이라고 하고 n의 자릿수를 d라고 하자. 그러면 str 함수의 시간 복잡도는 O(logn)으로 나타낼 수도 있고 O(d)로 나타낼 수도 있다.
• append의 시간 복잡도는 O(1)이다.
• insert, del, index, reverse는 모두 O(n)이다.
• sort 메소드와 sorted 함수의 시간 복잡도는 O(nlgn)이다.
• 리스트 슬라이싱의 시간 복잡도는 슬라이싱의 범위 길이에 비례한다. my_list[a:b]를 하면 시간 복잡도는 O(b−a)
• len 함수의 시간 복잡도는 O(1)이다.