알고리즘 - 알고리즘의분석: 시간복잡도

알고리즘의 분석: 시간복잡도

인프런 - 권오흠 강사님의 자료를 인용했습니다.

PPT자료링크  

https://s3.ap-northeast-2.amazonaws.com/inflearnattachment/algorithm/chap01_time_complexity.pdf

> 알고리즘의 분석

알고리즘의 자원(resource) 사용량을 분석 자원이란 실행 시간, 메모리, 저장장치, 통신 등 여기서는 실행시간의 분석에 대해서 다룸

>시간 복잡도(tiem complexity)

1.실행시간은 실행환경에 따라 달라짐 

• 하드웨어, 운영체제, 언어, 컴파일러 등 

2.실행 시간을 측정하는 대신 연산의 실행 횟수를 카운트 

3.연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현 

4.데이터의 크기가 같더라도 실제 데이터에 따라서 달라짐 

• 최악의 경우 시간복잡도 (worst-case analysis) 

• 평균 시간복잡도 (average-case analysis)

>점근적 분석

1.점근적 표기법을 사용 

• 데이터의 개수 n→∞일때 수행시간이 증가하는 growth rate로 시간복잡도를 표현 하는 기법 
• Θ-표기, Ο-표기 등을 사용 

2.유일한 분석법도 아니고 가장 좋은 분석법도 아님 

• 다만 (상대적으로) 가장 간단하며 
• 알고리즘의 실행환경에 비의존적임 
• 그래서 가장 광범위하게 사용됨

>점근적 분석의 예: 상수 시간복잡도

n에 관계없이 상수 시간이 소요된다. 이경우 알고리즘의 시간복잡도는 0(1)이다.

>점근적 분석의 예: 선형 시간복잡도

1.

선형 시간복잡도를 가진다고 말하고 O(n)이라고 표기한다.

2.

최악의 경우 시간복잡도는 O(n)이라고 한다.

>Quadratic

최악의 경우 배열에 저장된 모든 원소 쌍을 비교 하므로 비교 연산의 횟수는 n(n-1)/2이다. 최악의 경우 시간복잡도는 O(n2)으로 나타낸다.