빅오 표기법(big-O notation) - 시간 복잡도(time complexity)와 공간 복잡도(space complexity)

빅오 표기법 (big-O notation) 이란?

• 빅오 표기법은 알고리즘의 효율성을 표기해주는 표기법이다.(빅오는 최악의 시간 복잡도를 의미)
• 알고리즘의 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈 같은 기본 연산의 횟수를 의미한다.
• 빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용 된다.
• 시간 복잡도는 알고리즘의 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 공간(메모리) 효율성을 의미한다.)
• (참고) 시간과 공간 복잡도를 나타내는 방법으로는 점근 표기법이라고 해서 빅오(Big-O), 빅오메가(big-Ω),빅세타(big-Θ) 표기법이 있다.

빅오 표기법 주요 예제

• O(1) : 스택에서 Push, Pop
• O($\log_2 n$) : 이진트리
• O($n$) : for 문
• O($n\log_2 n$) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
• O($n^2$): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
• O($2^n$) : 피보나치 수열
  
  

이진트리

• [1, 2, 3, 4, 5, 6, 7, 8]가 주어졌고, 8이라는 숫자를 찾아야한다면

  • A : [1, 2, 3, 4], B : [5, 6, 7, 8]로 두개로 쪼개지고 B를 선택하게되고
  • A2 : [5, 6], B2 : [7, 8]로 두개로 쪼개지고 B2를 선택하게됨
  • A3 : [7], B3 : [8]로 두개로 쪼개지고 B3를 선택하게됨

• 이런식으로 반씩 쪼개지기 때문에 리스트[]의 길이를 $n$이라고 하고, 반씩 쪼개는 횟수를 $x$라고 했을때
  찾으려는 숫자인 [8]이 나올때는 반씩 쪼개는 걸 $x$번 반복하게되게됨
  원하는 숫자를 찾게됐을때 리스트 길이 n은 1이 됨

• 이를 수식으로 표현하자면

  • ${\cfrac{n}{2^x}}$ = 1

  • ${{n}}$ = ${2^x}$

  • ${{x}}$ = ${\log_2 {n}}$

피보나치

O($2^n$)인 경우

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

• $f(n-1) + f(n-2)$ $\dots$

• $f(n-1-1) + f(n-1-2) + f(n-2-1) + f(n-2-2)$
  $= f(n-2) + f(n-3) + f(n-3) + f(n-4)$

• $f(n-2-1) + f(n-2-2) + f(n-3-1) + f(n-3-2) + f(n-3-1) + f(n-3-2) + f(n-4-1) + f(n-4-2)$
  $=f(n-3) + f(n-4) + f(n-4) + f(n-5) + f(n-4) + f(n-5) + f(n-5) + f(n-6)$

• 이런식으로 함수 호출횟수가 2배씩 올라가기 때문에 O(2^n)이 됨

O($n$)인 경우

• 이경우 시간복잡도는 내려가지만 최근 값을 저장해두기 때문에 공간복잡도는 올라간다

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

메모

• 코딩테스트에서 데이터에 대한 정보 줄때 최대 n까지 주어진다. 이런 조건이 나올때 시간 복잡도를 생각해보자.
• 보통 1,000만이 넘어가면 굉장히 비효율적 => 10만개 데이터 2중 for문 => 10만 x 10만 = 1,000만

References

• https://noahlogs.tistory.com/27
• [알고리즘] Big-O 표기법