[자료구조와 알고리즘] 자료구조(5) - 시간복잡도

365.48km·2023년 1월 3일
0
post-thumbnail

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

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

  • 정수의 절대값 구하기
    - 1, -1 ->> 1
    • 방법1: 정수값을 제곱한 값에 다시 루트를 씌우기
    • 방법2: 정수가 음수인지 확인해서, 음수일 때만, -1을 곱하기

Key Ponint 💡
다양한 알고리즘 중 어느 알고리즘이 더 좋은지 분석하기 위해, 복잡도를 정의하고 계산한다.

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

  1. 시간 복잡도: 알고리즘 실행 속도 - 가장 중요
  2. 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈

Key Ponint 💡
프로그래밍에서 시간 복잡도에 가장 영향을 많이 미치는 요소는 반복문이다.

3. 알고리즘 성능 표기법

  • Big O (빅-오) 표기법: O(N)

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

    • 오메가 표기법은 알고리즘 최상의 실행 시간을 표기
  • Θ (세타) 표기법: Θ(N)

    • 오메가 표기법은 알고리즘 평균 실행 시간을 표기

Key Ponint 💡
시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 익혀야한다.

4. 대문자 O 표기법

  • 빅 오 표기법, Big-O 표기법 이라고도 부름

  • O(입력)

    • 입력 n 에 따라 결정되는 시간 복잡도 함수
    • O(1), O(lognlog n), O(n), O(nlognlog n), O(n2n^2), O(2n2^n), O(n!)등으로 표기함
    • 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
      • O(1) < O(lognlog n) < O(n) < O(nlognlog n) < O(n2n^2) < O(2n2^n) < O(n!)
        • 참고: log n 의 베이스는 2 - log2nlog_2 n
  • 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 됩니다.

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

    • n이 1이든 100이든, 1000이든, 10000이든 실행을

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

        • n에 따라 변경되는것이 없다.
               if n > 10:
                    print(n)
      • n에 따라, n번, n + 10 번, 또는 3n + 10 번등 실행한다: O(n)

             variable = 1
             for num in range(3):
                 for index in range(n):
                      print(index)
        • n에 따라, 반복문이 3 x n번 실행하게 됨
      • n에 따라, n2n^2번, n2n^2 + 1000 번, 100n2n^2 - 100, 또는 300n2n^2 + 1번등 실행한다: O(n2n^2)

             variable = 1
             for i in range(300):
                 for num in range(n):
                     for index in range(n):
                          print(index)
        • n에 따라, 300 x n x n + 1번 실행

profile
이게 마즐까?

0개의 댓글