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

oneofakindscene·2021년 8월 1일
0

CS

목록 보기
2/8

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

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

빅오 표기법 주요 예제

  • O(1) : 스택에서 Push, Pop
  • O(log2n\log_2 n) : 이진트리
  • O(nn) : for 문
  • O(nlog2nn\log_2 n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
  • O(n2n^2): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
  • O(2n2^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를 선택하게됨
  • 이런식으로 반씩 쪼개지기 때문에 리스트[]의 길이nn이라고 하고, 반씩 쪼개는 횟수xx라고 했을때
    찾으려는 숫자인 [8]이 나올때는 반씩 쪼개는 걸 xx번 반복하게되게됨
    원하는 숫자를 찾게됐을때 리스트 길이 n은 1이 됨

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

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

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

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

피보나치

O(2n2^n)인 경우

if(n <= 0)
    return 0;
else if(n == 1)
    return 1;
return f(n-1) + f(n-2);
  • f(n1)+f(n2)f(n-1) + f(n-2) \dots

  • f(n11)+f(n12)+f(n21)+f(n22)f(n-1-1) + f(n-1-2) + f(n-2-1) + f(n-2-2)
    =f(n2)+f(n3)+f(n3)+f(n4)= f(n-2) + f(n-3) + f(n-3) + f(n-4)

  • f(n21)+f(n22)+f(n31)+f(n32)+f(n31)+f(n32)+f(n41)+f(n42)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(n3)+f(n4)+f(n4)+f(n5)+f(n4)+f(n5)+f(n5)+f(n6)=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(nn)인 경우

  • 이경우 시간복잡도는 내려가지만 최근 값을 저장해두기 때문에 공간복잡도는 올라간다
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

profile
oneofakindscene

0개의 댓글