[파이썬][자료구조] 시간 복잡도

시간 복잡도

시간 복잡도 계산이 필요한 이유

알고리즘을 푸는데 정해진 정답은 없어 어떤 방식이 더 좋은지 고려하기 위해서 시간 복잡도를 계산해야 한다.

 

복잡도 계산 항목

1. 시간 복잡도 : 실행 속도
2. 공간 복잡도: 사용하는 메모리 사이즈
   시간 복잡도가 중요하다. 공간 복잡도는 요즘 잘 계산하지 않는다.

 

시간 복잡도 주요 요소

반복문이 가장 큰 영향을 미친다.

 

알고리즘 성능 표기법

• Big O 표기법 : O(N)
  • 가장 오래 걸리는 실행 시간을 계산
  • 가장 많이 사용함
  • 최악의 상황이라도, 이 정도 성능은 보장

Big-O 표기법

• 빅 오 표기법, Big-O 표기법 이라고도 부른다.

• O(입력)

  • 입력 n에 따라 결정된다.

  • O(1), O($log n$), O(n), O(n$log n$), O($n^2$), O($2^n$), O(n!)등으로 표기한다.

  • 입력 n의 크기에 따라 걸리는 시간이 기하급수적으로 변한다.

    • O(1) < O($log n$) < O(n) < O(n$log n$) < O($n^2$) < O($2^n$) < O(n!)
      • 참고: log n의 베이스는 2 - $log_2 n$

  • n에 따라 몇 번 실행되는지 계산하면 된다.

    • 무조건 2회 (상수회) 실행될 때 : O(1)

            if n > 10:
                 print(n)

    • n에 따라, n번, n + 5, 2n + 10번 등으로 실행할 때 : O(n)
      

      for num in range(2):
         for i in range(n):
            print(i)      

    • n에 따라, $n^2$, $n^2 + 100$, $100n^2 - 25$번 실행할 때: O($n^2$)
      

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

    • 시간 복잡도가 $2n^2 + 5n$일 때 O($n^2$) 로 가장 높은 차원으로 표기한다.

1부터 n까지의 합을 구할 때 시간 복잡도

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

sum(100)

5050

반복문이 n번 실행된다.
시간 복잡도 : O(n)

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

sum(100)

5050

반복문이 없다.
시간 복잡도 : O(1)

어떤 것이 더 좋은가?

O(1)이 시간이 더 적게 걸려서 좋다.