아래의 Wiki에서 가져왔으며, 각 O표기법 마다 의 영어 명칭과 예제를 정확히 알기 위해 아래에 표시
솔직히 아래의 Notation을 전부 이해하지는 못하겠으며, 아직도 혼동이 되고 있다.
이는 알고리즘을 개별 알고리즘을 분석하면서 알아내야 겠다.
Notation | Name | Example |
---|---|---|
constant | Determining if a binary number is even or odd; Calculating ; Using a constant-size lookup table | |
double logarithmic | Number of comparisons spent finding an item using interpolation search in a sorted array of uniformly distributed values | |
logarithmic | Finding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a Binomial heap | |
polylogarithmic | Matrix chain ordering can be solved in polylogarithmic time on a Parallel Random Access Machine. | |
fractional power | Searching in a kd-tree | |
linear | Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array; adding two n-bit integers by ripple carry | |
n log-star n | Performing triangulation of a simple polygon using Seidel's algorithm, or the union–find algorithm. Note that | |
linearithmic, loglinear, or quasilinear | Performing a fast Fourier transform; heapsort, quicksort (best and average case), or merge sort | |
quadratic | Multiplying two n-digit numbers by a simple algorithm; bubble sort (worst case or naive implementation), Shell sort, quicksort (worst case), selection sort or insertion sort | |
polynomial or algebraic | Tree-adjoining grammar parsing; maximum matching for bipartite graphs | |
L-notation or sub-exponential | Factoring a number using the quadratic sieve or number field sieve | |
exponential | Finding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent usingbrute-force search | |
factorial | Solving the traveling salesman problem via brute-force search; generating all unrestricted permutations of a poset; finding the determinant with Laplace expansion; enumerating all partitions of a set |
전체적인 O표기법을 설명
https://en.wikipedia.org/wiki/Big_O_notation
기본 O표기법 설명 및 복잡도 비교하는 법 설명
http://web.mit.edu/16.070/www/lecture/big_o.pdf
쉽게 간단히 O표기법 설명
https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
댓글 없음 :
댓글 쓰기