2017/05/31
数据结构与算法
表现形式:
1)逻辑结构（逻辑上是如何组织(即表示)数据的）
线性结构('均有顺序和链式两种实现')
如：线性表、栈(特殊的线性表)、队列(特殊的线性表)
集合结构
树形结构
图形结构
2)物理结构（物理上是如何组织(即存储,是指在内存中存储)数据的）
顺序存储结构
链式存储结构
注意：数据的存储结构应正确的反映数据的逻辑结构。
算法分析:是从统计学的角度来分析
时间复杂度：该算法对于输入规模(即输入次数 n)需要执行的次数，以此可以来反映算法的效率
T[n] = O[f(n)]
常见的：
O(1) 常数阶（基本操作次数为常数，没有循环）
O(n) 线性阶（单循环）
O(n^2) 平方阶（循环嵌套形成）
O(n^k) K方阶
O(x^n) 指数阶
O(logn) 对数阶
例程：
int i = 1; n = 100;
while(i < n) {
i = i * 2;
}
分析：该程序执行的次数设为 x
则， 1*2*2*...*2 < n
——>> 2^x < n
——>> x < logn
O(nlogn) 线性对数阶
注意：常见时间复杂度耗时次序
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
对于，从n^3往后的算法，对n的大小很敏感，稍微大一点，算法的执行时间都将成为噩梦
空间复杂度: 表示算法在整个运行过程中占用的存储空间
S[n] = O[f(n)]
辅助单元是常数个时，称此算法为原地工作，S[n]= O(1)
注意：通常情况下，我们追求的是时间效率，因此，可以考虑用增大空间开销来换取时间上的效率。
----------------来自《大话数据结构》-----------------
数据：是描述客观事物的符号，不仅包含数值类型的，还包含非数值类型的
数据元素(又称为'记录')：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。
数据项：一个数据元素可以由若干个数据项组成。可以简单的理解为数据元素的属性。(用来刻画一个数据元素的)
数据对象：是性质相同的数据元素的集合，它是数据的子集
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
简言之：可以反映出数据元素之间的组织关系(从逻辑上来说)
抽象数据类型(Abstract Data Type, ADT)：是指一个数学模型及定义在该模型上的一组操作
算法(Algorithm)：算法是描述解决问题的方法。
1.算法的5大特性:
• 输入 (零个或多个)
• 输出 (一个或多个)
• 有穷性 (在可忍受的时间内执行完毕！)
• 确定性 (相同的输入，对应特定的输出)
• 可行性 (算法的每一步都是可行，有限次后定可完成)
2.算法设计的要求
正确性：要能正确反映问题的需求，能够得到文通的正确答案。
注意：算法的正确性通常由数学方法证明，大部分情况下不可能用程序来证明
可读性：便于阅读、理解、交流
健壮性：当输入不合法时，算法应能做出相应处理，而不是产生异常或出现模型奇妙的结果(反映到机器上可能就是程序崩溃)
高效性: 越快执行完毕，越好
低存储量(占用的机器的内存小)
算法效率(主要是指执行时间)的度量方法
