알고리즘의 성능 분석(시간 복잡도, 공간 복잡도, 빅오 표기법)

 알고리즘의 성능 분석 방법

1. 수행 시간 측정

• 두 개의 알고리즘의 실제 수행 시간을 측정한다.
• 실제로 구현하여야 하며, 동일한 하드웨어를 사용해야 한다.

 

수행 시간 측정의 2가지 방법

 

2. 알고리즘의 복잡도 분석

• 알고리즘이 수행하는 연산의 횟수를 측정하여 비교한다.
• 실제로 구현하지 않아도 된다.
• 연산의 수행 횟수는 입력의 개수 n에 대한 함수이다.

 

2-1) 시간 복잡도

• 전체 소요 시간 = 컴파일 시간 + 실행 시간
• 방법: 전역 변수 count의 사용, 단계수 테이블 방식

 

단계별 테이블 방식의 예시

 

2-2) 공간 복잡도

• 공간 요구량 = 고정 공간 요구 + 가변 공간 요구
• 고정 공간: 프로그램 입출력의 횟수나 크기와 관계없는 공간
• 가변 공간: 해당 문제의 인스턴스(I)에 의존하는 공간

 

 

 

 Asymptotic Notation(점근 표기법)

점근 표기법의 종류

점근 표기법에는 빅오(함수의 상한), 빅오메가(함수의 하한), 빅세타(함수의 상한 및 하한) 표기법이 있는데, 그 중 가장 정밀한 것은 빅세타 표기법이지만 통상적으로는 빅오 표기법을 사용한다.

 

 빅오 표기법

빅오 표기법은 연산의 횟수를 대략적(점근적)으로 표기한 것이다. 시간복잡도 함수에서 차수가 가장 큰 항을 제외한 다른 항들은 상대적으로 무시될 수 있다.

O(n!) > O(2^n) > O(n^k) > O(n^3) > O(n^2) > O(nlogn) > O(n) > O(logn) > O(1)

 

※ 최선, 평균, 최악의 경우 => 최악의 경우가 가장 계산이 쉽고 의미가 있어 널리 사용된다.

 

 

 

 

출처) C언어로 쉽게 풀어쓴 자료구조