CS - 2. Asymptotic Notation (점근 표기법)

2. Asymptotic Notation (점근 표기법)

 

💡The efficiency of an algorithm depends on the amount of time, storage and other resources required to execute the algorithm. The efficiency is measured with the help of asymptotic notations.

An algorithm may not have the same performance for different types of inputs. With the increase in the input size, the performance will change.

The study of change in performance of the algorithm with the change in the order of the input size is defined as asymptotic analysis.

 

알고리즘의 효율성은 알고리즘을 실행하는 데 필요한 시간, 저장 공간 및 기타 리소스의 양에 따라 달라집니다. 효율성은 점근 표기법의 도움으로 측정됩니다.

알고리즘은 입력 유형에 따라 성능이 다를 수 있습니다. 입력 크기가 증가하면 성능이 달라집니다.

입력 크기 순서의 변화에 따른 알고리즘의 성능 변화를 연구하는 것을 점근 분석이라고 정의합니다.

 

 

3가지의 표기법

 

Big O notation

Big Θ notation(theta)

Big Ω notation(omega)

 

점근 표기법에는 

3가지의 표기법이 있습니다.

이번장에서는 점근표기법의 표기법의 종류와 어떤 상황에서 사용하는지 알아보겠습니다.

 

 

Big O notation

💡Big O Notation describes, how well an algorithm scales with the input size. It is used to describe the worst case scenario of an algorithm. It is used to compare algorithms and to determine which algorithm is better.

빅오 표기법은 알고리즘이 입력 크기에 따라 얼마나 잘 확장되는지를 설명합니다. 알고리즘의 최악의 시나리오를 설명하는 데 사용됩니다. 알고리즘을 비교하고 어떤 알고리즘이 더 나은지 판단하는 데 사용됩니다.

 

- 최악의 실행 시간

예)

선형 검색 알고리즘에서 최악의 경우는 찾고자 하는 원소가 배열의 마지막에 있을 떄입니다.

이 경우 실행 시간은 배열의 크기 n에 비례하므로, 빅 오 표기법으로 O(n)으로 표현됩니다.

 

Big Θ notation(theta)

💡 While Big O Notation refers to the upper bound of a function, Big Theta Notation refers to the exact bound of a function. Big Theta Notation is used to describe the exact growth rate of a function. It is denoted by the symbol Θ.

빅 O 표기법이 함수의 상한을 나타내는 반면, 빅 세타 표기법은 함수의 정확한 하한을 나타냅니다. 빅 세타 표기법은 함수의 정확한 성장률을 설명하는 데 사용됩니다. 이는 기호 Θ로 표시됩니다.

 

- 알고리즘의 평균 실행 시간

예)

버블 정렬 알고리즘은 모든 경우에 대해 실행 시간이 원소의 개수 n의 제곱에 비례하므로, 빅 세타 표기법으로  Θ(n^2)으로 표현됩니다.

 

Big Ω notation(omega)

💡 Big Omega notation is used to describe the lower bound of a function. It is the opposite of Big O notation. While Big O is used to describe the worst case scenario of an algorithm, Big Omega is used to describe the best case scenario of an algorithm.

빅 오메가 표기법은 함수의 하한을 설명하는 데 사용됩니다. 빅 O 표기법과 반대입니다. 빅 O는 알고리즘의 최악의 시나리오를 설명하는 데 사용되는 반면, 빅 오메가는 알고리즘의 최상의 시나리오를 설명하는 데 사용됩니다.

 

- 최선의 실행 시간

예)

이진 검색 알고리즘에서 최선의 경우는 찾고자 하는 원소가 배열의 중간에 있을 떄입니다.

이 경우 시간은 로그 시간이므로, 빅 오메가 표기법으로 Ω(log n)으로 표현됩니다.

Common Runtimes

• O(1) - Constant (상수)
• O(log n) - Logarithmic (로그형)
• O(n) - Linear (선형)
• O(n log n) - Linearithmic (선형로그)
• O(n^2) - Quadratic (이차식)
• O(n^3) - Cubic (세제곱)
• O(2^n) - Exponential (지수형)

def exponential(n):
    if n == 0:
        return 1
    return 2 * exponential(n - 1)

• O(n!) - Factorial (계승)

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

• O(n^k) - Polynomial (다항식)

def polynomial_algorithm(n):
    for i in range(n):
        for j in range(n):
            print(i, j)

 

 

https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84#%EB%A1%9C%EA%B7%B8_%EC%8B%9C%EA%B0%84_(Logarithmic_time)

시간 복잡도 - 위키백과, 우리 모두의 백과사전