算法复杂度分析与计算

数据结构是数据存储的方式并显示数据之间的关系。算法的必要条件是输入和输出数据，因此数据结构也是算法的必要条件。

健全的算法必须是有限的、确定性的和可执行的。算法也有好坏之分。例如，著名数学家高斯发现了算术级数的对称性，这使得他能够从算术数列的角度来计算和。

#include<stdio.h>
int main(){
    
	int ans =0,i;
	for (i=0;i<=100;i++){
    
		ans +=i;
	}
	printf("%d",ans);
	return 0;	
} 

#include<stdio.h>
int main(){
    	
	int a =(1+100)*(100/2);
	printf("%d",a);
	
} 

当计算从 1 到 100 的数字时，两种方法都会得到 5050，但显然第二种方法更简单。因此，算法也有优点和缺点。评价一个算法优劣的标准称为算法的复杂度，分为时间复杂度和空间复杂度。

程序执行时间表示一个程序运行所需要的时间，一个算法的执行时间大致上等千其所有语句执行时间的总和。

算法的执行时间受计算机、编译时间、硬件环境等影响，但这些因素与算法无关。因此，如果将每条语句的执行时间视为单位时间，那么所有语句执行的单位时间就是时间复杂度。

时间复杂度定义为算法执行时间的增长率O(n)。

句子频率定义为一条语句的重复执行次数f(n)。
由于时间为单位时间，那么对于任何执行次数（语句频度）均有
$$F（n）=1*n$$

n代表执行次数。

如果一段算法3000行，那么$$F（n）=1*3000$$
故执行时间的增长率为1，每次增加一个单位时间，所以时间复杂度也就最低。

规定时间复杂度用O(fn)表示，并规定常数的时间复杂度为O(1)即T(n) = O(1)。

时间复杂度的计算公式为T(n) = O(f(n)).

以下常见的时间复杂度计算是：

int i;
for (i=0;i<n;i++){
    
	s = s+i;    //执行n次
	i++;
}

语句频度：
$$F（n）=n+1$$
时间复杂度：
$$氧（n）=n$$

for(i=0;i<=n;i++){
    
	for(j=0;j<=n;j++){
    
		y++;
	}
}

上面算法中外层的语句频度为fn=n，内层的语句频度的时间复杂度为fn=n,因此整个程序的时间语句频度为n^2即fn=n^2故T(n) = O(n^2)。

for (i=0;i<=n;i=i*2){
    
	ans +=i;
}

上面程序只有一个循环，但是次循环的增量为i*2，在[0,100]的范围内，令语句频度为f(n)
$$2^{F（n）}<=n$$

$$F（n）<=我哦G_{2}n$$

所以时间复杂度为 ${\mathrm{loG}}_{2}n$。

算法的存储空间需求，采用渐近空间复杂度(Space
Complexity)作为算法所需存储空间的度量，称为空间复杂度。

除了自己的输入和输出之外，程序还需要存储产生的数据。前者取决于问题本身，与算法无关。后者占用的存储空间大小表示算法所需的存储容量大小。

for(i=O;i<n/2;i++) {
     
	t=a[i]; 
	a[i]=a[n-i-1]; 
	a[n-i一l]=t;
}

for (i=O; i<n; i++) {
    
	b[i]=a[n-i-1]; 
}
for(i=O;i<n;i++) {
    
	a [i] =b [i];
}

两个程序执行相同的功能，但前者只需要欺骗变量t，后者需要一个数组。空间复杂度的计算方法与时间复杂度的计算方法相同。

$$S（n）=氧（F（n））$$

对于第一个算法 f(n) = 1，S(n) = O(1)。第二个兄弟算法f(n) = n，S(n) = O(n)。

设单位空间为1，算法空间占用大小f(n)。如果 f(n) 不是常数，则 O(n) 取最大阶项。