算法和时间复杂度概念_分析 algorithm 1 的时间复杂度(用 θ 符号表示)

算法（algorithm）

是指令的集合，是为解决特定问题而规定的一系列操作，算法就是计算机解题的过程。
一个算法通常来说具有以下五个特性：

1. 输入：一个算法应以待解决的问题的信息作为输入。
2. 输出：输入对应指令集处理后得到的信息。
3. 可行性：算法是可行的，即算法中的每一条指令都是可以实现的，均能再有限的时间内完成。
4. 有穷性：算法执行的指令个数是有限的，每个指令优势再有限时间内完成的，因此整个算法也是再有限时间内可以结束的。
5. 确定性：算法基于特定的合法输入，其对应的输出是唯一的，即当算法从一个特定的输入开始，多次执行同一指令集结果总是相同的。
   举例：如何求1+2+3+…+100=?
   算法1：依次相加while do-while for
   算法2：高斯解法：首尾相加*50
   算法3：使用递归实现：sum(100)=sum(99)+100 sum(99)=sum(98)+99…sum(2)=sum(1)+2 sum(1)=1

评价算法优劣的根据：复杂度（时间复杂度和空间复杂度）
算法的复杂性体现再运行算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间资源，因此复杂度分为时间和空间复杂度。
时间复杂度是指执行算法所需要的计算工作量；
空间复杂度是执行这个算法所需要的内存空间。

时间复杂度（Time Complexity）

时间频度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试。
一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。
一个算法中的语句执行次数称为语句频度或时间频度，表示为T（n），n表示问题的规模

时间复杂度

但有时我们想知道它变化时成型什么规律，想知道问题的规模，而不是具体的次数，此时一i纳入时间复杂度，一般情况下，算法中基本操作重复执行的次数时问题规模n的某个函数用T（n）表示。
时间复杂度就是时间频度去掉低阶项和首项常数。
比如某个算法的时间频度时T（n）=10000nn+10n+3
但是时间复杂度时T（n）=O（nn）

最坏时间复杂度和平均时间复杂度

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间，鉴于平均复杂度
第一：难计算
第二：由很多算法的平均情况和最差情况的复杂度时一样的。
所以一般讨论最坏时间复杂度
为了进一步说明算法的时间复杂度我们定义O、Ω、Θ符号
O符号给出了算法时间复杂度的上界（最坏情况 《=）
Ω符号给出了时间复杂度的下届（最好情况》=）
Θ符号给出了算法时间复杂度的精确阶（最好和最坏时同一阶 = ）

时间复杂度计算

1. 找出算法中的基本语句；
   算法中执行粗疏最多的那条语句就是基本语句，通常时内层循环的循环体
2. 计算基本语句的执行次数的数量级；
   只需计算基本语句执行次数的数量级，之久以为着要保证基本语句执行次数的函数中的最高次幂正确即可，
   可以忽略所有低次幂和最好次幂的系数，这样能够简化算法分析，并且式注意力集中再最重要的一点上：增长率
3. 用大O记号表示算法的时间性能
   将基本语句执行次数的数量级放入大O记号中

时间复杂度距离

• 一个简单语句的时间复杂度O（1）。

int count = 0;
1

T（n）= 1
T（n）= O（1）

• 100个简单语句的时间复杂度也为O（1）。（100是常熟，不是去向无穷大的n）

int count = 0;
。。。
int count100 = 100；
1
2
3

T（n）= 1
T（n）= O（1）

• 一个循环的时间复杂度为O（n）

int n=8,count=0;
for(int i=1; i<10n+100;i++){
	count++;
}
1
2
3
4

T（n）= 10n+100
T（n）= O（n）

• 时间复杂度为O（log2 n）的循环语句

int n=8,count=0;
for(int i=1; i<n;i*=2){
	count++;
}
1
2
3
4

• 时间复杂度为O（n2）的二重循环

int n=8,count=0;
for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		count++;
	}
}
1
2
3
4
5
6

• 时间复杂度为O（nlog2 n）的二重循环

int n=8,count=0;
for(int i=1;i<=n;i*=2){
	for(int j=1;j<=n;j++){
		count++;
	}
}
1
2
3
4
5
6

• 时间复杂度为O（n2）的二重循环

int n=8,count=0;
for(int i=1;i<=n;i++){
	for(int j=1 ;   j<=i   ;j++){
		count++;
	}
}
1
2
3
4
5
6

1+2+3+4+。。。+n=（1+n）n/2 ==》T（n）= O（n2）

空间复杂度分析

空间复杂度分析1

int fun(int n){
	int i,j,k,s;
	s=0;
	for(i=0;i<=n;i++){
		for(j=0;j<=i;j++){
			for(k=0;k<=j;k++){
				s++;
			}
		}
	}
	return(s);
}
1
2
3
4
5
6
7
8
9
10
11
12

由于算法中临时变量的个数与问题规模n无关，所以空间复杂度均为S（n）=O（1）

空间复杂度分析2

void fun(int a[],int n, int k){
	//数组a共有n个元素
	int i;
	if(k==n-1){
		for(i=0;i<n;i++){
			printf("%d\n",a(i));//执行n次
		}
	}
	else{
		for(i=k ;i<n;i++){
			a[i]=a[i]+i*i;//执行n-k次
		}
		fun(a,n,k+1);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

此算法属于递归算法，每次调用本身都要分配空间，fun（a，n，0）的空间复杂度为O（n）

注意：

1. 空间复杂度相比时间复杂度分析很少
2. 对于递归算法来说，代码一般都比较简短，算法本身所占用的存储空间较少，但运行时需要占用较多的临时工作单元；若写成非递归算法，代码一般可能比较长，算法本身占用的存储空间较多，但运行时将可能需要较少的存储单元。