Home /etc/ 시간복잡도, 공간복잡도 (+ 빅O 표기법)
Post
Cancel

/etc/ 시간복잡도, 공간복잡도 (+ 빅O 표기법)



1. 시간복잡도


  • 알고리즘이 문제를 해결하기 위한 수행시간의 분석 결과인
    시간,연산의 횟수(스탭수)
  • 주로 최악의 경우(worst case)를 따져 Big O 표기법을 이용해 분석



2. 공간복잡도


  • 알고리즘의 메모리 사용량에 대한 분석 결과
  • 주로 최악의 경우(worst case)를 따져 Big O 표기법을 이용해 분석

  • 공간복잡도가 커졌을 경우?
    공간 복잡도는 보통 시간 복잡도보다 중요하게 생각되지 않는 경우가 많다.
    그러나 빅데이터 처리를 하는 경우, 공간 복잡도가 위와 같이 커지게 된다면,
    메모리에 한 번에 올라가지 않아 프로그램을 실행할 수 없는 문제가 발생할 수 있다.
    이 경우, 데이터를 나눠서 처리하고 다시 합치는 방법을 사용하게 된다.



3. Big O 표기법


Big-Oh Notation

예를 들어, 동전을 튕겨 뒷면이 나올 확률을 이야기 할 때
운이 좋으면 1번에 뒷면이 나오지만
운이 안 좋다면 n번 만큼 동전을 튕겨야 하는 경우가 발생한다.

최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라 부른다.


  • 알고리즘의 효율성을 상한선 기준으로 표기해주는 표기법
    • 값이 클수록, 그래프가 위로 향할수록 비효율적임을 의미

빅오표기법


빅오(Big-O), 빅오메가(big-Ω),빅세타(big-Θ) 표기법

  • 빅오: 상한선 기준
  • 빅오메가: 하한선을 기준
  • 빅세타: 상한선과 하한선의 사이를 기준



3-1. Big-O 표기법의 종류


3-1-1. O(1)

constant complexity

  • 입력값이 증가하더라도 시간이 늘어나지 않는다.
  • 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다.


3-1-2. O(n)

linear complexity

  • 입력값이 증가함에 따라 시간 또한 같은 비율로 증가
  • 예) 1중 for문


3-1-3. O(log n)

logarithmic complexity

  • O(1) 다음으로 빠른 시간 복잡도를 가짐
  • 예) 자료구조에서 Binary Search Tree
       ㄴ 2진 탐색트리는 노드를 이동할때마다 경우의 수가 절반으로 줄어든다.


3-1-4. O(n^2)

quadratic complexity

  • 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가
  • 예) 2중 for문


3-1-5. O(2^n)

exponential complexity

  • Big-O 표기법 중 가장 느린 시간 복잡도를 갖음
  • O(log n)복잡도 같은 경우는 선택할때마다 경우의 수가 절반으로 줄어들었지만,
    O (2^n)복잡도는 그 반대로 경우의 수가 2배씩 들어난다.



3-2 시간복잡도를 구하는 요령


  • 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
  • 컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
  • 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
  • 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
  • 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n * m) -> O (n²)
  • 컬렉션 정렬을 사용하는 경우 : O(n*log(n))



*빅-오 표기법 (Big-Oh Notation) O(n) 시간복잡도 함수 T(n)T(n)에서 가장 영향력이 큰 부분만을 따지는 표기법

*https://lgphone.tistory.com/46




(참고)



공부한 내용을 여러글과 책 읽은 내용을 바탕으로 정리하고 있습니다.
좋은 글로 저의 공부에 도움을 주시는 분들께 감사드립니다.

This post is licensed under CC BY 4.0 by the author.