Big-O

알고리즘의 효율성을 나타내는 지표로 알고리즘이 빨라젔는지, 메모리를 많이 잡아먹지는 않는지 알고리즘의 성능을 판단할 때 사용합니다. 시간에 대한 개념인 시간복잡도와 공간에 대한 개념인 공간복잡도가 있습니다.

시간 복잡도

Big-O에 대한 시간 개념으로 알고리즘의 수행시간이 얼마인지 나타냅니다. 수행되는 연산의 수를 가지고 계산하며 알고리즘에서 중요하지 않은 부분은 최대한 무시합니다.

알고리즘 계산에 속하는 연산
- 산술
- 비교
- 대입
Big-O에서 무시되는 것들
- 상수항
- 지배적이지 않은 항(EX. O(N^2 + N) => O(N^2))
자주 사용되는 실행시간
- O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) < O(n^n)

보통 알고리즘의 big-o를 표기할 때는 최악과 평균을 표시합니다.

공간 복잡도

알고리즘이 공간(메모리)를 얼만큼 필요로 하는지 나타냅니다. 크기가 N인 배열을 만들 때 공간 복잡도는 O(N)이 되고, NXN 배열을 만들 때 O(n^2)이 됩니다.

logN의 시간 복잡도

자주 사용되는 O(logn)을 예를 들어보겠습니다. O(logn)의 실행시간을 갖는 알고리즘은 대표적으로 Binary Search가 있습니다.

Binary Search
2^k = N을 만족하는 k
EX) 2^4 = 16 -> log16 = 4
EX) logN = k -> 2^k = N
어떠한 문제에서 원소의 개수가 절반씩 줄어든다면 O(logn)

재귀함수의 시간 복잡도 (Fibonacci 수열)

피보나치 수열은 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열입니다.

이걸 코드로 나타내면 다음과 같습니다.

f(n){
    if(n <= 0)
        return 0;
    else if(n == 1)
        return 1;
    return f(n-1) + f(n-2);
}

다수 호출로 이루어진 재귀함수에서의 수행시간은 보통 O(분기^깊이)로 표현됩니다.

f(n)의 시간 복잡도
- 2^0 + 2^1 + 2^3 + 2^4 + … 2^n-1 => 2^n -1
- 2의 승수의 합
- O(2^n)

피보나치 수열을 O(n)으로 만들 수도 있습니다.

f(n, r){
    if(n <= 0)
        return 0;
    else if(n == 1)
        return r[n] = 1;
    else if(r[n])
        return r[n];
    return f(n-1) + f(n-2);
}

캐시를 사용하는 방법입니다. 이미 계산된 것은 재 계산하지 않도록해서 중복되는 호출을 제거하면 각각 한번씩만 계산되고, 이후는 계산된 값을 사용하므로 O(N)이 되게 됩니다. Alt fibonaci

그림은 엔지니어대한민국 님의 유튜브에서 인용했습니다.

참고

코딩인터뷰 완전정복
엔지니어대한민국 유튜브