[자료구조] 시간복잡도, 공간복잡도

프로그램의 성능 평가에 프로그램을 실행하는 데 필요한 시간과 공간의 추정치를 분석하는 방법과 컴퓨터가 실제로 프로그램을

실행하는데 걸리는 시간을 측정하는 방법이 있다. 여러 프로그램을 비교하는 데 성능 측정 방법보다는 성능 분석을 사용한다.

공간적인 효율성과 시간적인 효율성이라는 복잡도를 평가한다.

공간 복잡도

---

공간 복잡도 (space complexity)는 프로그램을 실행시켜 완료하는 데까지 소요되는 총 저장 공간을 의미한다.

알고리즘에 사용되는 메모리 총량이라고 생각하면 쉽다. 공간 복잡도는 최악의 경우나 평균의 경우를 고려하여 표현한다.

공간 복잡도 = 고정 공간 + 가변 공간 |    특정 프로그램의 성능을 분석하기 위해서 공간 복잡도는 기억공간이 최악이나

평균적으로 얼마나 필요한지를 분석하는 방법이다.

시간 복잡도

---

시간 복잡도 (time complexity)는 프로그램을 실행시켜 완료하는 데까지 걸리는 시간을 의미하며, 컴파일 시간과 실행 시간을 모두

포함한다. 컴파일 시간은 프로그램마다 거의 고정적인 시간이 소요되고, 실행 시간은 컴퓨터의 성능에 따라 달라질 수 있으므로

실제 실행시간 보다는 명령문의  실행 빈도수에 따라 계산한다.

시간 복잡도 = 컴파일 시간 + 실행 시간

컴파일 시간 = 어떤 프로그램을 컴파일하는 데 소요되는 시간을 의미하며 , 프로그램의 크기와 복잡성, 컴파일러의 속도 및 하드웨어

의 성능에 따라 달라진다.

실행 시간 = 어떤 알고리즘 또는 프로그램이 입력을 받은 후 출력을 내고 종료하기까지 걸리는 시간을 의미, 기계어 명령을 인출하여

해독하고 실행하는 데 걸리는 시간을 말한다.

최악경우 분석(Worst-case Analysis)

평균경우 분석(Average-case Analysis)

최선경우 분석(Best-case Analysis)

아래는 버블 정렬의 시간 복잡도와 공간 복잡도이다. 

최선 : O(n)

평균  , 최악 :  O(n^2)

공간 복잡도 : O(1) 

Sort Algorithm Complexity Summery