• TOC {:toc}

이 글은 패스트 캠퍼스 기술면접 완전 정복 올인원 패키지 Online ‘Chapter 08. 시간 복잡도’의 강의내용을 정리하기 위해 강의 자료를 기반으로 작성한 글입니다.

강의 노트는 강의 구매자에게만 제공되는 자료이긴 하지만 잔재미 코딩의 2. 알고리즘 복잡도 표현 방법에서 동일한 자료를 제공하고 있기 때문에 해당 자료를 기반으로 정리한 글을 작성해서 올립니다. 혹시 문제가 되는 경우 바로 내릴 예정이니 알려주시면 감사하겠습니다.

내용을 이해하기 위한 개인적인 설명이나 해석이 있을 수 있기 때문에 되도록 원문을 참고해주시길 바랍니다. 잘못된 부분이 있다면 댓글이나 그 외 편하신 방법으로 알려주시면 감사하겠습니다.

시간 복잡도: 알고리즘 복잡도 표현 방법

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

  • 하나의 문제를 푸는 알고리즘은 다양할 수 있음
    • 정수의 절댓값 구하기
      • 1, -1 ->> 1
      • 방법 1: 정숫값을 제곱한 값에 다시 루트를 씌우기
      • 방법 2: 정수가 음수인지 확인해서, 음수일 때만, -1을 곱하기
  • 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함
    • 단순하게 생각하면 프로그램이 빠르게 실행되는 알고리즘이 좋은 알고리즘이다.

2. 알고리즘 복잡도 계산 항목

  • 시간 복잡도: 알고리즘 실행 속도
  • 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈

가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 함

  • 현재는 메모리의 가격이 많이 저렴해져서 공간 복잡도는 상대적으로 덜 중요해졌다.

알고리즘 시간 복잡도의 주요 요소

반복문이 지배합니다.

생각해보기: 자동차로 서울에서 부산을 가기 위해, 다음과 같이 항목을 나누었을 때, 가장 총 시간에 영향을 많이 미칠 것 같은 요소는?

  • 예시: 자동차로 서울에서 부산 가기
    1. 자동차 문 열기
    2. 자동차 문 닫기
    3. 자동차 운전석 등받이 조정하기
    4. 자동차 시동 걸기
    5. 자동차로 서울에서 부산 가기: 가장 영향이 크다.
    6. 자동차 시동 끄기
    7. 자동차 문열기
    8. 자동차 문닫기

마찬가지로, 프로그래밍에서 시간 복잡도에 가장 영향을 많이 미치는 요소는 반복문

입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행 시간을 지배함

알고리즘 성능 표기법

  • Big O (빅-오) 표기법: O(N)
    • 알고리즘 최악의 실행 시간을 표기
    • 가장 많이/일반적으로 사용함
    • 아무리 최악의 상황이라도, 이 정도의 성능은 보장한다는 의미이기 때문
  • Ω (오메가) 표기법: Ω(N)
    • 오메가 표기법은 알고리즘 최상의 실행 시간을 표기
  • Θ (세타) 표기법: Θ(N)
    • 오메가 표기법은 알고리즘 평균 실행 시간을 표기

시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 익히면 됨

3. 대문자 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_2n$
  • 단순하게 입력 n에 따라, 몇 번 실행이 되는지를 계산하면 됩니다.

    • 표현식에 가장 큰 영향을 미치는 n의 단위로 표기합니다.

      • 상수 번 곱하거나 더해주는 것은 크게 신경 쓰지 않는다.
    • n이 1이든 100이든, 1000이든, 10000이든 실행을

    • 무조건 2회(상수회) 실행한다: O(1)

        if n > 10:
             print(n)
      
    • n에 따라, n번, n + 10번, 또는 3n + 10번 등 실행한다: O(n)

      # 총 3n + 1번 실행
      variable = 1
      # 총 3n번 실행
      for num in range(3):
          # n번 실행
          for index in range(n):
              print(index)
      
    • n에 따라, $n^2$번, $n^2 + 1000$번, $100n^2 + 100$, 또는 $300n^2 + 1$번 등 실행한다: O($n^2$)

      # 총 300n^2 + 1번 실행
      variable = 1
      # 총 300n^2번 실행
      for i in range(300):
          # 총 n^2번 실행
          for num in range(n):
              # n번 실행
              for index in range(n):
                  print(index)
      
  • 빅 오 입력값 표기 방법

    • 예: 만약 시간 복잡도 함수가 $n^2 + 3n$ 이라면
      • 가장 높은 차수는 $n^2$
      • 상수는 실제 큰 영향이 없음
      • 결국 빅 오 표기법으로는 O($n^2$) (서울부터 부산까지 가는 자동차의 예를 상기)

4. 실제 알고리즘을 예로 각 알고리즘의 시간 복잡도와 빅 오 표기법 알아보기

1부터 n까지의 합을 구하는 알고리즘 작성해보기

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

  • 합을 기록할 변수를 만들고 0을 저장
  • n을 1부터 1씩 증가하면서 반복
  • 반복문 안에서 합을 기록할 변수에 1씩 증가한 값을 더함
  • 반복이 끝나면 합을 출력
def sum_all(n):
    total = 0
    for num in range(1, n + 1):
        total += num
    return total

sum_all(100) #  5050

시간 복잡도 구하기

  • 1부터 n까지의 합을 구하는 알고리즘 1
    • 입력 n에 따라 덧셈을 n 번 해야 함 (반복문!)
    • 시간 복잡도: n, 빅 오 표기법으로는 O(n)

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

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

sum_all(100) #  5050

시간 복잡도 구하기

  • 1부터 n까지의 합을 구하는 알고리즘 2
    • 입력 n이 어떻든 간에, 곱셈/덧셈/나눗셈 하면 됨 (반복문이 없음!)
    • 시간 복잡도: 1, 빅 오 표기법으로는 O(1)

어느 알고리즘이 성능이 좋은가요?

  • 알고리즘 1 vs 알고리즘 2
    • O(n) vs O(1)

이와 같이, 동일한 문제를 푸는 알고리즘은 다양할 수 있음 어느 알고리즘이 보다 좋은지를 객관적으로 비교하기 위해, 빅 오 표기법등의 시간복잡도 계산법을 사용함

이후 자료구조, 알고리즘부터는 빅 오 표기법으로 성능을 계산해보면서, 빅 오 표기법과 계산방법에 익숙해지기로 합니다.