공간복잡도 / 시간복잡도

공간복잡도 (Space Complexity)

효율적인 알고리즘을 판단하는 기준에는 공간복잡도와 시간 복잡도가 있습니다.

공간복잡도는 메모리를 얼마나 사용하는지에 관한 복잡도(RAM 사용량)입니다.

하지만 최근 대용량 컴퓨터가 많아짐에 따라 중요성이 많이 떨어졌습니다.

---

시간복잡도 (Time Complexity)

시간복잡도는 시간이 얼마나 걸리느냐에 관한 복잡도(CPU 사용량)입니다.

시간복잡도는 명령어들이 몇번이나 실행됬는지, 실행시간을 곱한 합계로 구할 수 있습니다.

최상의 경우, 최악의 경우, 평균 시간에 따라 3가지 경우로 표기되며,

표기법으로 빅오 표기법(최악의 경우), 오메가 표기법(최상의 경우), 세타 표기법(평균의 경우)이 존재합니다.

빅오 표기법은 최악의 경우(Worst Case)를 나타내는 표기법으로 알고리즘 분석에서 가장 많이 사용합니다.

일반적으로 O(n^2) 이상 부터 시간복잡도를 줄이기 위한 노력을 해야 합니다.

비교 : O(1) < O(Logn) < O(n) < O(nLogn) < O(n^2) < O(n^3) < O(2^n)

최고차항만 생각하여 계산    ex) n^2 + n +3 = O(n^2)