알고리즘 복잡도

1. 알고리즘 복잡도 계산이 필요한 이유

- 하나의 문제를 푸는 알고리즘은 무수히 많다. 이를 정량적으로 비교할 수 있어야 어떤 알고리즘이 효율적인지 알 수 있다. 이때 사용하는 것이 바로 알고리즘 복잡도 이다.

 

2. 알고리즘 복잡도 종류

- 시간복잡도 : 알고리즘 실행 속도, 반복문에 가장 큰 영향을 받는다.

- 공간복잡도 : 알고리즘이 사용하는 메모리 용량

- 시간복잡도가 가장 많이 쓰인다.

 

3. 알고리즘 성능 표기법 - Big 0 표기법: O(N)

- 입력 n에 따라 결정되는 시간복잡도 함수

- O(1), O(log n), O(n), O(nlog n), O(n²), O(2ⁿ), O(n!)등으로 표기함

- O(1)

• 반복문이 없는 알고리즘. 아래에서는 n이 100이든, 1000이든 무조건 2회만 실행한다.

if n > 10:
	print(n)

 

- O(n)

• n에 따라 n번, n+10번 등을 실행한다.

variable = 1
      for num in range(3):
          for index in range(n):
               print(index)

 

- O(n2)

• n에 따라 n²번 등을 실행한다. 

for i in range(300):
          for num in range(n):
              for index in range(n):
                   print(index)

 

 

 

4. 알고리즘 예제

- 1부터 n까지의 합을 구하는 알고리즘

- 알고리즘 1 : 시간복잡도 O(n)

def sum_all(n):
    total = 0
    for num in range(1, n + 1):
        total += num
    return total

 

- 알고리즘2 : 시간복잡도 O(1)

def sum_all(n):
    return int(n * (n + 1) / 2)

 

- 시간복잡도는 알고리즘2가 현저히 낮다. 즉 더욱 효율적이다.