시간, 공간 복잡도

알고리즘과 자료구조를 공부하기에 앞서 필수가 되는 지식 중 하나인 시간 복잡도와  공간 복잡도에 대해 정리해보자

---

복잡도

복잡도란 쉽게 말해 알고리즘의 성능과 효율성을 나타내는 척도이다. 복잡도를 나타내는 표기법으로는 O(빅오), Ω(오메가), Θ(세타)등이 있고, 주로 빅오 표기법과 세타 표기법이 많이 사용된다.
복잡도에는 수행 시간을 평가할 수 있는 시간 복잡도와 사용 공간을 평가할 수 있는 공간 복잡도가 있다. 

---

시간 복잡도(Time Complexity)

시간 복잡도란 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수를 나타낸다. 알고리즘의 성능 평가는 아래와 같은 case를 나누어 평가한다.

CASE	설명
최선의 경우 (Best Case)	최적의 입력 상태에서 작업을 완료하는데 걸린 연산 횟수가 가장 적은 경우
최악의 경우 (Worst Case)	최악의 입력 상태에서 작업을 완료하는데 걸린 연산 횟수가 가장 많은 경우
평균의 경우 (Average Case)	여러 경우의 수를 고려하여, 총 연산 횟수를 시행 횟수로 나눈 경우

알고리즘 분석 시, 평균의 경우와 최악의 경우가 가장 많이 활용된다. 알고리즘이 복잡해질수록 최악의 경우로 성능 평가를 한다.

 

공간 복잡도(Space Comlexity)

공간 복잡도란 프로그램 실행과 완료에 얼마나 많은 메모리가 필요한지를 측정해준다. 알고리즘을 실행시키기 위해 필요한 공간은 크게 두가지로 나뉜다.

• 고정 공간
  - 코드가 저장되는 공간, 알고리즘을 실행시키기 위해 시스템이 필요로 하는 공간 등 알고리즘과 무관한 공간
• 가변 공간
  - 변수를 저장하기 위한 공간 등 문제를 해결하기 위해서 알고리즘이 필요로 하는 공간

---

빅오 표기법(Big-O notation)

빅오 표기법은 알고리즘 효율성을 상한선 기준으로 표기하는 점근 표기법 중 하나이다. 알고리즘의 효율성은 값이 클수록 비효율적임을 나타내기 때문에 최악의 경우를 고려하기엔 가장 좋은 표기법이다. 빅오 표기법의 특징은 아래와 같다

• n이 충분히 크다고 가정하고, 상수항 같은 사소한 부분은 무시한다.
  => O(2n)은 O(n)으로 간주
• 가장 영향력이 큰 n항 이외의 항은 무시한다.
  => O(n^2 + 2n)은 O(n^2)으로 

시간 복잡도의 복잡도 순서는 아래와 같다. 상수함수가 가장 좋은 시간 복잡도이며, 지수함수로 갈수록 복잡해진다. 

시간 복잡도를 구하는 Tip!!

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

 입력값인 N의 크기에 따라 허용가능한 시간복잡도를 표로 나타내면 아래와 같다.

N의 크기	허용 시간 복잡도
N < 11	O(N!)
N < 25	O(2^N)
N < 100	O(N^4)
N <  500	O(N^3)
N <  3,000	O(N^2lgN)
N <  5,000	O(N^2)
N <  1,000,000	O(NlgN)
N <  10,000,000	O(N)
그 이상	O(lgN),O(1)

참조 : https://velog.io/@welloff_jj/Complexity-and-Big-O-notation