数据结构与算法（ Java 描述）

• 一个算法还必须具备以下要素：
  • 输入：待处理的信息，即对具体问题的描述。比如，对于上述三个例子来说，输入分别是“任 意给定的直线以及其上的一点”、“任意给定的一条线段”以及“由 n 个可比较元素组成的序 列”。
  • 输出：经过处理之后得到的信息，即问题的答案。比如，对于上述三个例子来说，输出分别 是我们所要得到的“垂直线”、“三等分点”以及“完全有序的序列”。
  • 确定性：任一算法都可以描述为由若干种基本操作组成的序列。在垂直线算法中，“取等长 绳索”、“联结绳索”、“将绳结固定于一点”、“沿特定方向拉直绳索”等操作都属于基本操作。 在三等分线段算法中，基本操作就是欧氏作图法所允许的所有尺规操作。而在起泡排序算法 中，基本操作就是图灵机所允许的各种操作：“读取某一元素的内容”、“比较两个元素的大 小”以及“修改某一元素的内容”等等。
  • 可行性：在相应的计算模型中，每一基本操作都可以实现，且能够在常数时间内完成。
  • 有穷性：对于任何输入，按照算法，经过有穷次基本操作都可以得到正确的输出。

• 时间频度

  • 一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

• 时间复杂度

  • 在时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。
  • 算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。
  • 记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
  • T (n) = Ο(f (n)) 表示存在一个常数C，使得在当n趋于正无穷时总有 T (n) ≤ C * f(n)。
  • 简单来说，就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大(小于等于)。也就是说当n趋于正无穷时T (n)的上界是C * f(n)。
  • 其虽然对f(n)没有规定，但是一般都是取尽可能简单的函数。例如，O(2n^2+n +1) = O (3n^2+n+3) = O (7n^2 + n) = O ( n^2 ) ，一般都只用O(n^2)表示就可以了。
  • 在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。
  • 注意到大O符号里隐藏着一个常数C，所以f(n)里一般不加系数。如果把T(n)当做一棵树，那么O(f(n))所表达的就是树干，只关心其中的主干，其他的细枝末节全都抛弃不管。
  • 算法中语句执行次数为一个常数，则时间复杂度为O(1)
  • 按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log n),线性阶O(n), 线性对数阶O((n * log n),平方阶O(n^2)，立方阶O(n^3),…， k次方阶O(n^k),指数阶O(2^n)。

• 复杂度举例：

  • O(1) 常数级复杂度，也就是说程序运行的时间与需要处理的数据大小无关。通常把比较大小、加减乘除等简单的运算都当做常数级复杂度。 值得注意的是，在处理大数（二进制下数据长度超过32位或者十进制下超过8位）时，将加减乘除等运算当做常数复杂度不再适用。
  • O(log n) 将一个10进制整数转化为2进制整数
  • O(n)：判断一个元素是否属于一个大小为n的集合/列表；找出n个数中的最大值；
  • O(n * log n) 快速排序法
  • O(n^2) 最直白的两两比较然后排序方法，需要n*(n-1)/2次比较，所以是O(n^2)级。
  • O(2^n) 列出所有长度为n的0,1字符串之类的穷举计算
  • O(n!) 列出n个元素的全排列之类的穷举计算