[자료구조] 1강. 자료구조의 개념 - 알고리즘 성능의 분석과 측정

알고리즘의 성능 분석

실행시간 분석

알고리즘을 실행하는데 필요한 실행시간을 추정하여 알고리즘의 성능을 분석(performance analysis)

실행 시간의 예측

　- 알고리즘의 실행 횟수를 O(n)이라고 표현

　- 같은 O(n)을 가진다고 해서 같은 실행 시간을 갖는 것이 아니라 실행 시간의 유사한 증가 경향

실행메모리 분석

알고리즘을 실행하는데 필요한 공간(메모리)을 추정하여 알고리즘의 성능을 분석(performance analysis)
실행 메모리의 예측

　- 알고리즘의 공간 복잡도(space complexity)는 프로그램을 실행시켜서 완료하는 데 필요한 총 메모리 공간

　- 고정 공간은 프로그램의 크기나 입출력의 횟수에 관계없이 컴파일 시에 결정되어 프로그램의 실행이 끝날 때까지 고정적으로 필요한 메모리 공간

　- 가변 공간은 프로그램의 실행 과정에서 동적으로 할당되어야 하는 자료 구조와 변수들을 위해 필요한 메인메모리 공간

　- Sp = Sc + Se (공간복잡도 = 고정공간 + 가변공간)

알고리즘의 성능 측정

성능 측정

컴퓨터가 실제로 프로그램을 실행하는데 걸리는 시간을 측정하여 알고리즘의 성능을 측정(performance measurement)

실행 시간의 측정

　- 실제로 실행 시간을 시계로 잰다는 것

　- 실제로 실행될 수 있는 프로그램(실행 파일)이 있어야 함

　- 시스템 시계(system clock)을 이용