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

알고리즘 속도의 기준 ->  "프로그램 수행 시간" 부적합

- 프로그램 수행시간은 사용한 프로그래밍 언어, 하드웨어, 운영체제, 컴파일러, 등의 요소에 의해 바뀔 수 있기 때문

- 프로그램 실제 수행 시간이 다양한 입력에 대한 실행 시간을 반영하지 못하기 때문

 

 

알고리즘 수행시간 측정

반복문이 수행되는 횟수로 측정

  - 반복문이 지배한다.(dominate) : 반복문이 전체 코드를 좌지우지함

 

시간 복잡도 (time complexity)

- 가장 널리 사용되는 알고리즘의 수행 시간 기준

- 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력 크기에 대한 함수로 표현한 것

( 기본적인 연산 : 더 작게 쪼갤 수 없는 최소 크기의 연산)

- 중첩된 반복문의 내부에 있는 기본적 연산 : 더 쪼갤 수 X -> 시간 복잡도의 대략적인 기준

- 시간 복잡도가 높다 = 알고리즘 수행 시간이 더 빠르게 증가한다. 

- 시간 복잡도가 낮은 알고리즘 : 입력이 커지면 커질수록 더 효율적 ( 낮다고 해서 언제나 더 빠른것 X) 

- 입력 종류에 따라 수행시간 변화

 

입력의 종류에 따른 수행시간 변화 

아래 코드의 경우, 반복문이 실행되는 횟수는 찾는 원소의 위치에 따라 달라짐

//array[i] = element 인 첫 i를 반환한다. 없으면 -1을 반환한다. 
int firstIndex(const vector<int>&array, int element){
	for(int i=0;i<array.size();++i){
		if(array[i]==element)	return i;
	return -1;
}

   (1) 최선의 수행시간

       - 찾으려는 원소가 배열의 맨 앞에 있을 때

       - 반복문의 수행횟수 : 1

   (2) 최악의 수행시간

       - 배열에 해당 원소가 없을 때 

       - 반복문의 수행횟수 : N

   (3) 평균적인 경우의 수행시간

       - 존재할 수 있는 모든 입력의 등장 확률이 모두 같다고 가정

       - 주어진 배열이 항상 찾는 원소를 포함한다 가정

               -> 반환 값의 기대치 : 약 N/2, 평균적인 수행횟수 : N/2

최악의 수행시간 or 수행시간의 기대치 주로 사용

 

 

Big-O Notation(빅 오 표기법 = 대문자 O 표기법 = 빅 O 표기법)

- 전체 수행시간에 영향을 미치지 않는 상수부분은 무시하고 반복문의 반복수만 고려