복잡도 (Complexity)
알고리즘의 복잡도를 판단하는 척도에는 시간 복잡도와 공간 복잡도가 있다.
시간복잡도는 실행되는데에 수행하는 연산을,
공간복잡도는 얼마나 많은 메모리가 필요한지 표현한다.
빅오 표기법의 특징
시간복잡도 표기법에는 빅오,빅오메가,빅세타 표기법이 있고 각각
최악,최상,평균의 실행시간을 알려준다.
빅오는 최악의 성능(최소한으로 보장되는 성능)을 표기할 수 있다.
영향을 주는 미미한것들은 배제하고 표기한다.
-
상수항을 무시
어떤 알고리즘이 O(N+5)의 복잡도를 가졌으면 상수를 생략해 O(N)으로 표기한다. -
계수도 무시
어떤 알고리즘이 O(3N)의 복잡도를 가졌으면 계수를 생략해 O(N)으로 표기한다. -
최고차항만 표기
어떤 알고리즘이 O(3N^3+2N^2+N+5)의 복잡도를 가졌으면 O(N^3)으로 표기한다.
빅오 표기법의 종류
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 제곱.
참고링크 https://blog.chulgil.me/algorithm/
각 종류마다 예시도 잘 나와있다.
