时间复杂度练习

3.时间复杂度练习

练习1：

// 计算Func2的时间复杂度？
void Func2(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N ; ++ k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

解析：时间复杂度为O(N)。用函数表达式来表示（N表示执行次数）：F(N)=2* N+10。用大O的渐进表示法需要去掉加法常数，2*N+10是属于N这个量级的，N的系数无论多大都要改为1，因为当N无限大时，系数对结果影响不大，所以时间复杂度为O(N)。

练习2：

// 计算Func3的时间复杂度？
void Func3(int N, int M)
{
	int count = 0;
	for (int k = 0; k < M; ++ k)
	{
		++count;
	}
	for (int k = 0; k < N ; ++ k)
	{
		++count;
	}
	printf("%d\n", count);
}

解析：时间复杂度为O(N+M)。具体运行次数为F(N)=N+M；用大O的渐进表示法估算之后时间复杂度为O(N+M)，因为N和M都是属于同一个量级的，所以M不能省略。

练习3：

// 计算Func4的时间复杂度？
void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++ k)
	{
		++count;
	}
	printf("%d\n", count);
}

解析：时间复杂度为O(1)。具体运行次数为100次，是常数级，根据大O的渐进表示法时间复杂度为O(1)。

练习4：

// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character );

解析：时间复杂度为O(N)。strchr函数作用为在一个串中查找给定字符的第一个匹配之处，并且返回一个指向该字符串中第一次出现的字符的指针，如果字符串中不包含该字符就返回NULL指针。 主要实现过程为：

while(*str++)
{
	if(*str==character)
		return str;
	}
return NULL;

在这种情况下时间复杂度就要区分为最好情况和最坏情况以及平均情况。假设字符串中共有n个字符，最好情况是第一次就找到，时间复杂度为O(1)；最坏情况是在最后一次才找到或者没有找到，时间复杂度是O(N)；平均情况下整体来看时间复杂度为O(N/2)。==但是在实际中，一般情况下关注的是最坏运行情况==。所以数组中搜索数据时间复杂度为O(N)。