빅오표기법(Big-O)

빅오표기법(Big-O)

• 불필요한 연산을 제거하여 알고리즘분석을 쉽게 할 목적으로 사용된다.
• Big-O로 측정되는 복잡성에는 시간과 공간복잡도가 있다.

시간복잡도

• 입력된 N의 크기에 따라 실행되는 조작의 수

공간복잡도

• 알고리즘이 실행될때 사용되는 메모리의 양

Big-O 복잡도 표

시간 복잡도

• 가동의 성과
• 시간복잡도에서 중요하게 보는 것은 가장 큰 영향을 미치는 n의 단위이다.

  1             O(1)   --> 상수
  2n + 20       O(n)   --> n이 가장 큰영향을 미친다.
  3n^2          O(n^2) --> n^2이 가장 큰영향을 미친다.
  

  시간복잡도의 문제 해결 단계를 설정했다면 가능하다.

  O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
  O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
  O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
  O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
  O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
  O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.
  

O(1)

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

O(n)

• 입력값이 증가함에 따라 시간 또한 선형적으로 같은 비율로 증가하는 것을 의미한다.
• 입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시킬 때 1초의 100배인 100초가 걸리는 알고리즘의 경우, O(n)의 시간복잡도를 가진다.

O(log n)

• 빅오 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
• BST(Binary Search Tree)의 경우, 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다. 이 경우 O(log n)의 시간 복잡도를 가진다.

O(n^2)

• 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

O(2^n)

• Big-O 표기법중 가장 느린 시간 복잡도를 가진다.
• 재귀로 구현한 피보나치 수열이 대표적인 O(2^n) 알고리즘이다.