2편 알고리즘 시간 복잡도 분석

1. 왜 필요한가

- 알고리즘의 수행 속도를 대략적으로 측정하기 위해서

- A 알고리즘이 B 알고리즘 보다 빠르다 느리다 얼마만에 수행이 된다 등

※ 왜 프로그램 수행 속도가 아닌 알고리즘의 수행 속도를 사용하는가?

- 프로그램 수행 속도는 하드웨어, OS, 컴파일러, 언어 등에 따라 바뀔 수 있기 때문

- 위의 외적인 이유를 같게 하더라도 어떤 STL을 썼는가, 파라미터, 반복문 내 수행되는 명령문의 개수 등에 따라도 바뀔 수 있기 때문

- 프로그램 수행 속도는 다양한 입력에 대한 실행 시간을 반영하지 못함(입력이 커지면 수행 속도도 달라지기 때문)

2. 속도 측정 기준

- 반복문이 돌아가는 횟수를 기준으로 함

※ 반복문을 제외한 나머지는?

- 입력의 크기가 충분히 크다면 반복문을 제외한 나머지 명령문의 수행 횟수는 전체 명령문의 수행 횟수에서 비율이 점점 줄어들 것이기 때문

 

- 입력의 크기에 따라 알고리즘 내 반복문의 수행 횟수가 달라지기 때문에 "입력의 크기에 대한 함수"로 표현 =>시간 복잡도 표현의 시작

3. 알고리즘 "시간 복잡도"의 표현과 예제

- Big-O Notation

※구술로 말할때는 Order 라고도 함

- Big-Ω

- Big-Θ

- Big-O 계산 방법 : 가장 큰 항만 남김, 상수 제외

※ 단, 알고리즘 문제를 풀면서 상수가 중요한 경우도 있으니 복잡하지 않으면 상수도 포함하여 계산하는 것도 나쁘지 않음

- 예제 : selection sort, insertion sort

1) selection sort

#include<iostream>
#include<vector>
using namespace std;

void selectionSort(vector<int>& arr){
	for (int i = 0; i < (int)arr.size(); i++){
		int minIndex = i;

		for (int j = i; j < (int)arr.size(); j++){
			if (arr.at(minIndex) > arr.at(j))
				minIndex = j;
		}

		swap(arr[i], arr[minIndex]);
	}
}

int main(void){
	vector<int> a(10, 0);
	
	for (int i = 0; i < (int)a.size(); i++)
		a[i] = (rand() % 10);

	for (int i = 0; i < (int)a.size(); i++)
		cout << a.at(i) << " ";
	cout << "\n";

	selectionSort(a);
	for (int i = 0; i < (int)a.size(); i++)
		cout << a.at(i) << " ";
	cout << "\n";
	return 0;
}

<src 1 : selection sort>

  : (N-1) + (N-2) + ... + 1 = ½N(N-1) = ½N^2 - ½N => O(N^2)

2) insertion sort

#include<iostream>
#include<vector>
using namespace std;

void insertionSort(vector<int>& arr){
	for (int i = 0; i < (int)arr.size(); i++){
		int j = i;
		while (j > 0 && arr[j] < arr[j-1]){
			swap(arr[j], arr[i]);
			j--;
		}
	}
}

int main(void){
	vector<int> a(10, 0);
	
	for (int i = 0; i < (int)a.size(); i++)
		a[i] = (rand() % 10);

	for (int i = 0; i < (int)a.size(); i++)
		cout << a.at(i) << " ";
	cout << "\n";

	insertionSort(a);
	for (int i = 0; i < (int)a.size(); i++)
		cout << a.at(i) << " ";
	cout << "\n";

	return 0;
}

<src 2 : insertion sort>

  : 1 + 2 + ... + N-2 + N-1 => O(N^2)

4. 시간 복잡도 어림짐작

- 대충 때려 맞추기(개인적으로 가장 많이 이용하는 방법) => 반복의 횟수가 약 1억번(2^20, 10!) 이면 1초에 실행 된다고 판단

  (단, 반복문 안이 길면 그보다 더 걸리고 짧으면 그보다 더 적게 걸림)

  : 1개가 끝나는데 걸리는 시간 * 총 개수

  : selection sort에서 1개가 정렬되려면 최악 N * 총 배열 개수가 N = N^2

  : insertion sort에서 1개가 정렬되려면 최악 N * 총 배열 개수가 N = N^2

  : Map에서 중복되지 않고 모든 칸을 가는 경우 = N^2

  : 선택 하고 안하고의 문제 = 2^N (선택의 경우가 3, 4... 이라면 3^N, 4^N 즉, 경우의 수)

                      (fig 1)

- fig 1 에 있는건 연산 결과 1억번이 나오는 N의 입력 크기

  ex) 1만^2 = 1억

공간복잡도 분석

- 알고리즘 문제 해결전략 1편 중 -

- 저작권 문제시 삭제하겠습니다 -