파이썬 시간복잡도 이해하기

알고리즘 시간복잡도가 필요한 이유는

하나의 문제를 푸는데 알고리즘이 다양할 수 있다.

복잡도를 통해 효율적인 알고리즘을 구현할 수 있다.

- 시간복잡도 : 알고리즘 실행속도를 말한다.

- 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈를 말한다.

- 시간복잡도는 반복문이 여러개 생길경우 많이 발생한다.

시간복잡도는 빅오 표기법을 사용한다.

O(1) < O( 𝑙𝑜𝑔𝑛 ) < O(n) < O(n 𝑙𝑜𝑔𝑛 ) < O( 𝑛2 ) < O( 2𝑛 ) < O(n!)

1. O(n)의 시간복잡도를 가지는 1부터 n까지의 합을 구하는 알고리즘

# 1부터 n까지의 합을 구하는 알고리즘1
 
def sum_all(n):
    total = 0
    for num in range(1, n + 1):
        total += num
    return total
 
print(sum_all(100)) # 5050 
 
# 시간복잡도  O(n)
# 입력 n에 따라 덧셈을 n 번 해야 함

2. O(1)의 시간복잡도를 가지는 1부터 n까지의 합을 구하는 알고리즘

# 1부터 n까지의 합을 구하는 알고리즘 2
 
def sum_all(n):
    return int(n * (n + 1) / 2)
 
print(sum_all(100)) # 5050
 
# 시간복잡도  O(1)
# 반복문이 없으므로 입력이 n이어도 O(1)

같은 결과를 내는 메소드라도 시간복잡도가 적은 O(1)이 효율적인 알고리즘이라고 할 수 있다.