[자료구조/알고리즘] 시간 복잡도

🖥 시간 복잡도

• 프로그램을 작성할 때 입력의 크기에 따라 프로그램이 계산하는 횟수가 크게 달라진다.
  입력된 자료의 양과 알고리즘 실행에 걸리는 시간 사이에는 어떠한 관계가 있는데 이를 '시간 복잡도'라고 부른다.

Ex) 자연수 N이 주어졌을때 1~N까지의 합을 구하는 프로그램

case 1]

res = 0
N = int(input())

for i in range(1, N+1):
    res += i

print(res)

case 2]

N = int(input())
res = N * (N+1) // 2

print(res)

---

case 1] O(N)의 시간 복잡도

• N=1,000 이라면 덧셈이 1,000번 일어나고, N=1,000,000 이라면 덧셈이 1,000,000번 일어나게 된다.
  ✔계산하는 횟수가 N에 비례

case 2] O(1)의 시간 복잡도

• n(n+1)2 인 수학 공식을 이용하여 합을 계산했다.

• N=1,000이든, N=1,000,000이든 무조건 덧셈 한 번과 곱셈 한 번, 나눗셈 한 번만을 하게 된다.
  ✔N에 아무 관계 없는 상수 시간 안에 계산이 처리

---

시간복잡도가 큰 알고리즘들은 더 크고 많은 데이터를 처리할 때 훨씬 더 오랜 시간이 걸리게 된다. 이 계산 횟수를 정확하게 측정하기 어렵기 때문에 Big O 표기법을 사용한다.

📌 Big O 표기법

• 입력된 데이터의 갯수가 n개일 때 2n+7번 계산하는 알고리즘과 2n번 계산하는 알고리즘이 있다고 하자. n이 커지면 둘 사이의 차이는 사실상 없어진다.

  ex)n이 1000000이면, 숫자 2000007, 2000000의 차이는 크지 않다.

• O 표기법으로 나타내면 (2n+7) = O(2n)
  ✔상수만큼의 시간 차이는 무시

• n번 계산하든, 7n+1312번 계산하든, 142857n번 계산하든 모두 O(n)로 나타내는 것이다! 비슷한 이유로, 2n3+12451n2+33nlog⁡n+151511번 계산하는 알고리즘의 시간 복잡도는 O(2n)이다.

---

• 자주 등장하는 알고리즘의 시간 복잡도들이다. 위의 알고리즘이 가장 시간 복잡도가 낮고 아래의 알고리즘이 가장 시간 복잡도가 높은 알고리즘이다.

O(1) 상수 형태. n의 값에 상관없이 일정한 양의 계산만 한다.
O(log⁡n) 로그 형태
O(n) 선형
O(nlog⁡n) 선형로그 형태
O(n2),O(n3),⋯ 다차 형태
O(2n) 지수 형태
O(n!) 팩토리얼 형태