10/19/2016

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

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

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

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

NotationNameExample
constantDetermining if a binary number is even or odd; Calculating ; Using a constant-size lookup table
double logarithmicNumber of comparisons spent finding an item using interpolation search in a sorted array of uniformly distributed values
logarithmicFinding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a Binomial heap

polylogarithmicMatrix chain ordering can be solved in polylogarithmic time on a Parallel Random Access Machine.

fractional powerSearching in a kd-tree
linearFinding 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
log-star nPerforming triangulation of a simple polygon using Seidel's algorithm, or the union–find algorithm. Note that 
linearithmic, loglinear, or quasilinearPerforming a fast Fourier transformheapsortquicksort (best and average case), or merge sort
quadraticMultiplying 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 algebraicTree-adjoining grammar parsing; maximum matching for bipartite graphs

L-notation or sub-exponentialFactoring a number using the quadratic sieve or number field sieve

exponentialFinding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent usingbrute-force search
factorialSolving 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/

댓글 없음 :