Big O

성능 순서 : O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)

O(n^2)

버블정렬, 선택정렬, 삽입정렬

O(nlogn)

병합정렬, 힙정렬, 퀵정렬

O(1) 오원의 시간복잡도 알고리즘

입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘
ex) n[0] == 0 ? 0 : null
시간복잡도가 동일한 알고리즘

O(logn) - 이진검색(binary search)

절반씩 줄어듬

func(k, arr, start, end) {
    if (start > end) return -1;
    m = (start + end) / 2;
    if (arr[m] == k) returm m;
    else if (arr[m] > k) func(k, arr, start, m-1);
    else return func(k, arr, m+1, end);
}

O(n)

입력 데이터의 크기에 비례해서 처리시간이 걸리는 알고리즘

//ex) 
for i=0 < n.length

시간복잡도가 일정하게 상승하는 알고리즘

O(n^2)

입력데이터의 크기에 비례하면서 n * n 의 처리시간이 걸리는 알고리즘

//ex)
    for i=0 < n.length
        for j=0 < n.length

시간복잡도가 점점상승하는 알고리즘

O(nm)

입력데이터의 크기에 비례하지만 다른 변수 두개가 들어오는 경우이기 때문에 n * m

//ex)
    for i=0 < n.length
        for j=0 < m.length
        //(두번째 for문이 클수도 작을 수도 있음)

시간복잡도가 점점상승하는 알고리즘

O(n^3)

//ex)
    for i=0 < n.length
        for j=0 < n.length
            for k=0 < n.length

O(n) : 직선, O(n^2) : 면적, O(n^3) : 큐빅

O(2^n) - 피보나치수열