알고리즘- 시간복잡도 분석(Time complexity Analysis)

알고리즘의 효율성을 분석 할때 시간복잡도를 많이 사용한다.

일반적으로, 알고리즘의 실행시간은

1.입력의 크기(input size)가 커지면 증가하고

2.총 실행시간은 단위연산(+,-,x,/)이 몇번 수행되는가에 비례한다.

 

● inputsize에만 영향을 받는 경우

#include <iostream>

using namespace std;
int main()
{
	int n, sum = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		sum = sum + i;
	}
	cout << sum;
}

이 알고리즘은 input-value에 무엇을 주든 단위연산은 n번 실행된다.

이 처럼 입력의 값(input value)에 상관없이 실행횟수가 일정한 경우

T(n)을 입력크기n일때 단위연산이 실행하는 횟수로 정의를 하고
여기서 T(n)을 일정시간복잡도(every-case time complexity)라고 한다.

하지만 몇몇 경우에서 시간복잡도는 input size에 의존할뿐만아니라 input value에도 의존한다.

●input value 의존하는 경우

#include <iostream>
#include <vector>
using namespace std;
int search(int n,int snum);
vector<int>F;
int snum = 9;
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		F.push_back(i);
	}
	cout<<search(n,snum);
}
int search(int n,int snum)
{
	for (int i = 0; i < n; i++)
	{
		if (F[i] == snum)
		{
			return snum;
		}
	}
	return 0;
}

이 경우에 n값과 snum값이 따라 시간 복잡도가 달라진다.

만약 snum이 F의 첫원소라면 단위연산은 한번만 일어난다.

그리고 snum이 F의 원소가 아니라면 단위연산은 n번 일어난다.

W(n)을 입력크기 n에 대하여 알고리즘이 실행할 최대 단위연산의 횟수라고 정의한다.

그러면 W(n)은 알고리즘의 최악 시간 복잡도(worst-case time complexity)라 하고,

W(n)을 구하는 과정을 최악 시간 복잡도 분석이라고 한다.

알고리즘의 효율성을 분석할 때 보통 최악 시간 복잡도로 분석하는 경우도 있지만 

평균적으로 얼마나 실행하는지 측정하는것이 일리가 있을 때도 있다.

 

A(n)을 입력크기 n에 대해서 알고리즘이 수행할 단위연산의 평균횟수로 정의한다.

A(n)을 알고리즘의 평균 시간복잡도(average-case time complextiy)라 하고

A(n)을 구하는 과정을 평균 시간복잡도 분석이라고 한다.

 

●최선 시간 복잡도

B(n)을 입력크기 n에 대해서 알고리즘이 실행할 단위연산의 횟수라고 정의한다.

B(n)은 알고리즘의 최선시간복잡도(best-case time complextiy)라 하고,

B(n)을 구하는 과정을 최선 시간복잡도 분석이라고 한다.

#include <iostream>
#include <vector>
using namespace std;
int search(int n,int snum);
vector<int>F;
int snum = 9;
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		F.push_back(i);
	}
	cout<<search(n,snum);
}
int search(int n,int snum)
{
	for (int i = 0; i < n; i++)
	{
		if (F[i] == snum)
		{
			return snum;
		}
	}
	return 0;
}

만약 input-value가 F의 첫번쨰 원소인 F[0]이라면 n에 크기에 상관없이 단위연산은 한번만 실행할것이다.

 

하지만 최선시간복잡도 분석은 알고리즘의 시간복잡도를 분석하는데 잘 사용하지 않는다.

오히려 최악,평균 시간 복잡도 분석을 더 자주 채택한다.