数据结构：逻辑结构and物理结构
逻辑结构（四大）：
1.集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他不三不四的关系。
2.线性结构：线性结构中的数据元素之间的是一对一的关系。
3.树形结构:树形结构中数据元素之间存在一种一对多的层次关系。
4.图形结构：图形结构的数据元素是多对多的关系。
物理结构：
实际：如何将数据元素存储到计算机的存储器中。
数据元素存储方式：
1.顺序存储（比如数组机构：数据元素存放在连续的单元里）
2.链式存储结构（例如领号，相比顺序存储更为灵活。）
算法特性：
1.输入：可以零个或多个输入（也就是参数）
2.输出：算法至少有一个或多个输出。输出形式：打印输出或返回一个值或者多个值。
3.有穷性
4.确定性：算法的每个步骤都有确定的含义，不会出现二义性，只有一条执行路径。
5.可行性：算法的每一步都必须是可执行的，也就是说，每一步都能够通过执行有限次数完成。（即遇到各种都可以执行，如果有不能执行的环境，要注明）
算法设计要求：
正确性：（四个层次）
1.没有语法错误。
2.对于合法输入都能够产生满足要求的输出。
3.对于算法程序对于非法输入能够产生满足规格的说明。
4.对于刁难性测试输入都有满足要求的输出结果。
可读性
健壮性
尽量提高效率和内存
分析时间复杂度：
1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中，只保留最高阶项。
3.如果最高阶项是存在且不是1，则去除与这个项相乘的常数。
4.得到的最后结果就是大O阶。
例子：
int sum=0;
int n=100;
printf("I love fishc.com");
printf("I love fishc.com");
printf("I love fishc.com");
printf("I love fishc.com");
printf("I love fishc.com");
printf("I love fishc.com");
sum=(1+n)*n/2;
这段代码的大O是多少。
答案：0(1)
线性阶：一般含有非嵌套循环设计线性阶，线性阶就是随着规模n的扩大，对应计算次数呈直线增长。
例如：
int i,n=100,sum=0;
for(i=0;i<n;i++){sum=sum+i;}
他的循环的时间复杂度为O(n)。
平方阶（嵌套）：O（n^2）
三层嵌套：O(n^3)
平方阶2.0：
int i,j,n=100;
for(i=0;i<n;i++){
for(j=i;j<n;j++){printf("i love fish .com");}
}
次数为：n+（n-1）+（n-2）+。。。。+1=n（n+1）/2
也就是n^2/2+n/2。根据上面的规律得到O(n^2)
对数阶：
int i=1，n=100；
while（i<n）{i=i*2;}
解答：2*x=n，所有x=log(2)n，所以得到 O（log n）
int i,j,n=100;
for(i=0;i<n;i++){for(j=i;j<n;j++){printf("i love fish .com");}}
for(i=0;i<n;i++){for(j=i;j<n;j++){printf("i love fish .com");}}
也就是2n^2，得到O(n^2)
。。。阶>立方阶平方阶>线性阶>对数阶>常数阶
常用的时间复杂度所耗费的时间：
O(1)<O(log n)<O(nlog n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n*n)
平均运行时间是期望的运行时间。
我们提到的运行时间是最坏情况的运行时间
当直接要让我们求复杂度时，通常指的是时间复杂度。
网友评论