算法------时间复杂度

程序=数据结构＋算法

数据结构：是要处理的信息
算法：处理信息的步骤

算法的基本概念：

算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。也就是说算法是处理计算机中的信息，以便于解决实际问题。

算法的特性：

有穷性：一个算法必须在执行有穷步之后结束，且每一步都可在有穷时间内完成。
算法必须是有穷的，但程序可以是无穷的。

确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。

可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。

输入：一个算法有零个或多个输入，这些输入取之于某个特定的对象的集合。

输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

‘好算法’的特点：

正确性：能够正确的解决问题。

可读性：应具有良好的可读性，以便于让人们能够理解。

注：算法可以是伪代码，甚至是文字，但必须满足“无歧义”的描述解决问题的步骤。

健壮性：输入非法数据时，算法能适当的做出反应或进行处理，而不会输出一些非法结果等。

高效率和低存储需求：高效率：执行速度快，时间复杂度低。低存储需求：不费内存，空间复杂度低。

算法时间复杂度：

事先预估算法时间开销T（n）与问题规模n的关系（T表示‘time’）

举例：

#include
void loveyou(int n)//n为问题规模
{
	int i = 1;//执行1次
	while (i <= n)//执行3001次
	{
		i++;//执行3000次
		printf("I LOVE YOU%d", i);//执行3000次
	}
	printf("I LOVE YOU More than %d\n", n);//执行一次
}
int main()
{
	loveyou(3000);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间开销T（n）与问题规模n的关系：T（3000）=1+3001+3000*2+1
将3000替换为n:T(n)=3n+3

因为这个程序的时间开销T和问题规模n的关系表达式比较简单，所以我们比较容易计算他两之间的关系，但如果是T(n)=n*3+2n2+12n+3这种比较复杂的呢？还需要带值计算吗？

当然不是！对于这种比较复杂的式子，我们可以直接忽略表达式中低阶的部分，只保留高阶的部分即可。

举例：

通过上述三种不同的表达式，我们不难看出，当时间规模（n）足够大时，精确计算产生的值和只计算高阶部分产生的值近似相等，不会有很大的误差。

对于时间复杂度的度量，我们可进行简化：

只保留阶数更高的部分！

T1(n)=O(n)
T2(n）=O(nn)
T3(n)=O(nn*n)

常见的数量级之间的阶数关系：

O(1)

当然，你也可以根据数学函数的图像进行了解。
由图可知，常数函数的时间复杂度最低，因此它的算法是最优秀的，其次对数，幂函数等。

依然以上述实例为例，我们在分析时间复杂度的时候，是一行一行进行分析，显然，这只适用于代码量比较少的情况。

如果此时我们在其插入1000行顺序执行（不带有循环）的代码，那么此时T（n）的常数部分需要多加1000，但是我们上面又讲到，在分析时间复杂度的时候，只需要关注高阶部分，常数可以忽略。

那么可以由此得出一个结论：顺序执行的代码只会影响常数项，可以忽略

含有单层循环程序的时间复杂度：

对上述实例的时间复杂度进行分析，我们得到如下关系：
T(n)=3n+3等价于T(n)=O（n）,我们此时来看循环语句中的任意一条，它执行了3000次等于n的值。

那么可以由此得出一个结论：只需要找出循环中的一个基本操作分析它的执行次数和n的关系即可

	#include
void loveyou(int n)//n为问题规模
{
	int i = 1;//执行1次
	while (i <= n)//执行3001次
	{
		i++;//执行3000次
		printf("I LOVE YOU%d", i);//执行3000次
	}
	printf("I LOVE YOU More than %d\n", n);//执行一次
}
int main()
{
	loveyou(3000);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

含有嵌套循环程序的时间复杂度：

我们对上述代码进行了修改，在while循环中还嵌套了一层循环。

void loveyou(int n)
{
	int i = 1;
	while (i <= n)
	{
		i++;
		printf("I LOVE YOU%d", i);
		for (int j = 1; j <= n; j++)
		{
			printf("I am Iron Man\n ");
		}
	}
	printf("I LOVE YOU More than %d\n", n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

和单层循环的分析方法相同，分别取两个循环中的一条任意语句。

外层循环该语句的执行次数等于n.

printf("I LOVE YOU%d", i);
1

内层循环该语句的执行次数为n*n次

printf("I am Iron Man\n ");
1

那么可以由此得出一个结论：如果有多层嵌套循环，只需要关注最深循环循环了几次

练习1：

void loveyou(int n)
{
	int i = 1;
	while (i < n)
	{
		i=i*2;
		printf("I LOVE YOU%d\n", i);
	}
	printf("I LOVE YOU More than %d\n", n);
}
1
2
3
4
5
6
7
8
9
10

通过上面的学习，你可以尝试分析这个算法的时间复杂度。

分析过程如下：

练习2：

void loveyou(int n)
{
	printf("I LOVE YOU More than %d\n", n);
	int i = 1;
	while (i < n)
	{
		if (Flag[i] == n)
			printf("I LOVE YOU%d\n", i);
	}
}
//Flag数组乱序存放1-n这些数
int Flag[n]={1.....n};
loveyou(Flag,n);
1
2
3
4
5
6
7
8
9
10
11
12
13

分析过程如下：

算法执行时间与输入的数据有关：

最坏时间复杂度：最坏情况下算法的时间复杂度

平均时间复杂度：所有输入实例等概率出现的情况下，算法的期望运行时间

最好时间复杂度：最好情况下算法的时间复杂度