Devcommon

Big-O Complexity

  1. 1. Big-O 분석법 (Big-O analysis)
  2. 2. Big-O 분석의 적용
  3. 3. Big-O 알고리즘의 종류
    1. 3.0.1. O(1)
    2. 3.0.2. O(log n)
    3. 3.0.3. O(n)
    4. 3.0.4. O(n log n)
    5. 3.0.5. O(n^2)
    6. 3.0.6. O(n^c)
    7. 3.0.7. O(c^n)
    8. 3.0.8. O(n!)
  • 참조

    • Big-O 분석법 (Big-O analysis)

    입력 값의 개수에 따라 알고리즘이 수행되는데 걸리는 시간을 바탕으로 알고리즘의 효율성을 평가하는 실행 시간 분석법.

    Big-O 분석의 적용

    1. 입력 값이 무엇인지 확인하고 어떤 것을 n으로 놓아야 할지 결정한다.
    2. 알고리즘에서 수행해야 할 연산 횟수를 n의 식으로 표현한다.
    3. 차수가 제일 높은 항만 남긴다.
    4. 모든 상수 인수를 없앤다.

    Big-O 알고리즘의 종류

    O(1)

    상수 실행 시간(constant running time)

    가장 빠른 알고리즘이며 이 경우는 거의 없다.

    1
    2
    3
    def constant(n):
        result = n * n
        return result

    O(log n)

    로그 알고리즘(logarithmic algorithm)

    실행 시간이 입력 크기의 log에 비례해서 늘어나는 알고리즘.

    1
    2
    3
    4
    5
    6
    def logarithmatic(n):
        result = 0
        while n > 1:
            n //= 2
            result += 1
        return result

    O(n)

    선형 알고리즘(linear algorithm)

    실행 시간이 입력크기에 비례하는 알고리즘.

    • O(n)

      1
      2
      3
      4
      5
      def linear(n, A):
          for i in xrange(n):
              if A[i] == 0:
                  return 0
          return 1

    • O(n + m)

      1
      2
      3
      4
      5
      6
      7
      def linear(n, m):
          result = 0
          for i in xrange(n):
              result += i
          for j in xrange(m):
              result += j
          return result

    O(n log n)

    초선형 알고리즘(superlinear algorithm)

    속도가 선형 알고리즘과 다항식 알고리즘의 중간쯤이다.

    O(n^2)

    이차 알고리즘(quadratic algorithm)

    입력 크기의 제곱으로 시간이 늘어난다.

    1
    2
    3
    4
    5
    6
    def quadratic(n):
        result = 0
        for i in xrange(n):
            for j in xrange(i, n):
                result += 1
        return result

    O(n^c)

    다항식 알고리즘(polynomial algorithm)

    입력 크기가 늘어나면 실행 시간이 빠르게 늘어난다.

    O(c^n)

    지수 알고리즘(exponential algorithm)

    다항식 알고리즘보다 실행 속도가 빠르게 늘어난다.

    O(n!)

    팩토리얼 알고리즘(factorial algorithm)

    가장 느린 알고리즘으로 n의 값이 작다고 해도 사용이 힘든 수준으로 느려진다.

    참조

    Share