一、基本知识

计算机科学	早期定义为:研究算法的科学
计算机科学	近期定义为:研究数据的科学

程序=算法+数据结构
数据结构是设计OS、DBMS、编译等系统程序和各种应用程序的重要基础。
常见的数据结构有:数组、栈、队列、表、串、树、图和文件等。
数据是什么？
①杂乱的数据不能表达和交流信息
②数据之间是有联系的
③数据之间是有结构的；
④在某种数据的结构上可以定义一组运算
程序设计的基本要素：

• 数据的各种逻辑结构和物理结构,以及它们之间的相应关系
• 并对每种结构定义相适应的各种运算
• 设计出相应的算法
• 分析算法的效率

二、数据结构

数据(Date)：所有能被计算机处理的符号的集合。
数据元素(Data Element)：数据这个集合中的单个个体。
数据项(Data Item)：数据元素常常被分为若干个数据项，数据项是数据具有意义的最小单位。
数据对象(Data Object)：具有相同特性的数据元素的集合。

---

数据结构(Data Structure)：是带有结构的数据元素的集合。
逻辑结构(Logical Structure)：指数据元素之间的结构关系。
物理结构(Physical Structure)：指数据结构在计算机内存中的表示。
物理结构的存放直接决定了逻辑结构的选择。

三、算法分析

什么是算法
算法是一个有限的指令集,遵循指令流可以完成特定的功能。
算法的基本特性：

特性	解释
有穷性	算法经有限步后结束
确定性	下一步必须是明确的
可行性	每一步是可执行的

如何衡量一个正确算法的好坏？
算法与程序的区别

• 算法是解决问题的一种方法或一个过程,考虑如何将输入转换成输出，一个问题可以有多种算法。
• 程序是用某种程序设计语言对算法的具体实现。

---

主要区别在:有穷性、正确性和描述方法
程序可以是无穷的，例如OS。
算法是有穷的;程序可以是错误的，算法必须是正确的;
程序是用程序设计语言描述，在机器上可以执行;
算法还可以用框图、自然语言等方式描述。

---

衡量的三个标准：
运行所花费的时间（算法的时间特性);
所占用存储空间的大小（算法的空间特性）;
其他（可读性、易调性、健壮性、可移植性等)
时间和空间特性的巨大改进源于更好的数据结构或算法。

• 语句频度（Frequency Count）
  语句可能重复执行的最大次数
• 时间复杂度（Time Complexity）
  设算法中所有语句的语句频度为t(n),
  f(n)是当n趋近于无穷大时与t(n)为同阶无穷大，
  则算法的时间复杂度T(n)=O(f(n))(总是考虑最坏情况)
  其中:n为算法计算量或称为规模（size）;
  f(n)是运算时间随n增大时的增长率;
  O(f(n))是算法时间特性的量度。
  

---

为什么要计算时间复杂度？
设:A1，A2和A3是求解同一问题的不同算法,其时间复杂度分别为:O(n)， O(nlogn)， O(N!)。
C1和C2为计算机，且C2的计算速度是C1的10倍。

复杂度	C1执行时间	C2执行时间	执行时间的关系
O(n)	N11	N21	N21 = 10*N11
O(nlogn)	N12	N22	N22=10*N12
O(N!)	N13	N23	N23=N13+小常数

不必追求高效算法,低效算法可由高速计算机来弥补的看法，是错误的。