数据结构是数据的存储方式，显示数据的关系，而算法必要的条件是输入和输出数据，因此数据结构也是算法的必要条件。
一个健全的算法必须具备有穷性，确定性，可执行性。算法也分好坏之分，例如著名数学家高斯发现了算数级数的对称性，从而能够从等差数列的角度计算求和。
#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
f(n) = 1*n
f(n)=1∗n
n表示执行次数。
如果一段算法3000行，那么
f
(
n
)
=
1
∗
3000
f(n) = 1*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
f(n) = n + 1
f(n)=n+1
时间复杂度：
O
(
n
)
=
n
O(n) = n
O(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
2^{f(n)} <= n
2f(n)<=n
f
(
n
)
<
=
l
o
g
2
n
f(n) <= log_2 n
f(n)<=log2n
所以时间复杂度为
log
2
n
\log_2 n
log2n。
算法的存储空间需求，采用渐近空间复杂度(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
)
=
O
(
f
(
n
)
)
S(n) = O(f(n))
S(n)=O(f(n))
对于第一个算法f(n) = 1 ，S(n) = O(1)。第二哥算法f(n) = n, S(n) = O(n)。
令单位空间1，算法空间占用大小f(n) ,若f(n) 不为常数，则O(n)取最大阶数项。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/156127.html
