Jeonghun (James) Lee

10/19/2016

Big O 표기법 (O notation ) 명칭정리

1. O표기법 관련 영문 명칭 및 예제

아래의 Wiki에서 가져왔으며, 각 O표기법 마다 의 영어 명칭과 예제를 정확히 알기 위해 아래에 표시

솔직히 아래의 Notation을 전부 이해하지는 못하겠으며, 아직도 혼동이 되고 있다.
이는 알고리즘을 개별 알고리즘을 분석하면서 알아내야 겠다.

Notation	Name	Example
$O(1)$	constant	Determining if a binary number is even or odd; Calculating $(-1)^{n}$ ; Using a constant-size lookup table
$O(\log \log n)$	double logarithmic	Number of comparisons spent finding an item using interpolation search in a sorted array of uniformly distributed values
$O(\log n)$	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
$O((\log n)^{c})$ $\scriptstyle c>1$	polylogarithmic	Matrix chain ordering can be solved in polylogarithmic time on a Parallel Random Access Machine.
$O(n^{c})$ $\scriptstyle 0<c<1$	fractional power	Searching in a kd-tree
$O(n)$	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
$O(n\log ^{*}n)$	n log-star n	Performing triangulation of a simple polygon using Seidel's algorithm, or the union–find algorithm. Note that $\log ^{}(n)={\begin{cases}0,&{\text{if }}n\leq 1\\1+\log ^{}(\log n),&{\text{if }}n>1\end{cases}}$
$O(n\log n)=O(\log n!)$	linearithmic, loglinear, or quasilinear	Performing a fast Fourier transform; heapsort, quicksort (best and average case), or merge sort
$O(n^{2})$	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
$O(n^{c})$	polynomial or algebraic	Tree-adjoining grammar parsing; maximum matching for bipartite graphs
$L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ $\scriptstyle 0<\alpha <1$	L-notation or sub-exponential	Factoring a number using the quadratic sieve or number field sieve
$O(c^{n})$ $\scriptstyle c>1$	exponential	Finding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent usingbrute-force search
$O(n!)$	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