시간복잡도와 공간복잡도

최대환·2022년 5월 12일
0

알고리즘

목록 보기
8/8

시간복잡도

  • 문제를 해결하는데 걸리는 시간과 입력한 함수 관계로, 시행 횟수를 센다.
  • 상대적으로 불필요한 연산을 제거하여 알고리즘의 분석을 조금 더 간편하게 하는 목적으로 표기하는 방법.

Big-O 표기법

  • 최악의 경우를 계산한다.
  • 계수와 낮은 차수의 항을 제외시키는 방법

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(n)

예제1

리스트 길이인 N만큼 시행횟수를 반복하기 떄문에 O(n)이다

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

예제2

N/2만큼 반복해서 O(n)이다.

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

예제3

O(3n)임으로 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(n^2)

이중 for문 같은 경우 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^3)

삼중 for문 같은 경우 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])

O(lg n)

예제1

1에서 2배로 lg n만큼 늘려나가면 n이 된다.

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

예제2

n을 몇번 반토막을 내야 1이되냐면 lg n만큼이다.

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

선형탐색 시간 복잡도 계산해보기

for 문안에서 some_list의 개수만큼 돌아감으로 시간복잡도는 O(N)이다.

def linear_search(element, some_list):

    for i in range(len(some_list)):
        if element == some_list[i]:
            return i

이진탐색 시간 복잡도 계산해보기

이진탐색은 최악의 경우 N길이의 리스트를 lgN만큼 반복한다.

def binary_search(element, some_list):
    start_index, end_index = 0, len(some_list) - 1

    while start_index <= end_index:
        mid_index = (start_index + end_index) // 2

        if some_list[mid_index] == element:
            return mid_index
        elif some_list[mid_index] < element:
            start_index = mid_index + 1
        elif some_list[mid_index] > element:
            end_index = mid_index - 1

    return None

헷갈릴 수 있는 log

log는 좀 헷갈리는 개념인데
Log_a(b)
b를 a로 몇번 나눠야하 되나?
라고 생각하면 될꺼같다.
예를들어 log_2(N)은
N길이의 리스트를 몇번 반토막 내야 1(최악의 경우 자료의 길이는 1이 됨으로)이 될 수 있나? 라고 생각하면 된다

보통 log_2(N)은 lgN이라고 사용한다.

주요 시간복잡도

공간복잡도

O(1)

result 는 O(1)이다.

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

O(n)

every_other의 공간복잡도는 O(n/2)여서 O(n)이다.

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

O(n^2)

a,b는 정수값임으로 O(1)이다.
products의 공간복잡도는 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)
profile
나의 개발지식 output 공간

0개의 댓글