数据结构与算法之概论

数据结构

相互之间存在一种或多种特定关系的数据元素的集合。研究数据结构，关心的是数据对象的描述以及相关操作函数的实现。

数据

是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。如整型、浮点型等数值类型，以及声音、图像等非数值类型。

数据元素

是组成数据的、具有一定意义的基本单位，在计算机中通常作为整体处理。也被称作记录。

数据项

一个数据元素可以由若干个数据项组成。它是数据不可分割的最小单位。

数据对象

是性质相同的数据元素（即有相同的数量和类型的数据项）的集合，是数据的子集。

常见的数据结构

线性数据结构：向量vector（顺序存储）、链表list（链式存储）、栈stack和队列queue（优先队列）。
半线性数据结构：二叉树、搜索树（二叉搜索树BST、AVL树、B树、红黑树）、竞赛树等。
非线性数据结构：图。
哈希表hashtable、字典dictionary。

抽象数据类型

数据类型：指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
抽象数据类型：指一个数学模型及定义在该模型上的一组操作。可以理解为C++中的类class。它体现的是程序设计中问题分解、抽象和信息隐藏的特性。

抽象数据类型的标准格式

ADT 抽象数据类型名
Data
    数据元素之间逻辑关系的定义
Operation
    操作1
    操作2
    ...
endADT

算法

算法是解决指定问题求解步骤的描述。在计算机中是指基于特定的计算模型，旨在解决某一信息处理问题而设计的一个指令序列。

计算或信息处理

指借助某种工具，按照一定的规则，以明确而机械的形式进行。

算法中的计算模型就是计算机，即信息处理工具。

算法必须具备的几大要素

输入：待处理的信息或问题。
输出：经处理的信息，即答案。
正确性：的确可以解决指定的问题。
确定性：任何一个算法都可以描述为一个由基本操作组成的序列。
可行性：每一基本操作都可实现，且能在常数时间内完成。
有穷性：对于任何输入，经有限次的基本操作，都可以得到输出。

一个好的算法

正确，即符合语法，能够编译、链接。

能够正确处理简单的、大规模的、一般性的、退化的、任意合法的输入。
健壮，能够辨别不合法的输入并做适当处理，而不致非正常退出。
可读，结构化 + 准确命名 + 注释 + …。
效率，运行速度尽可能快，用到的存储空间尽可能少。

常见的算法

查找

顺序查找、二分查找、插值查找、斐波那契查找、分块查找和哈希查找等。
排序

冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序和希尔排序等。
递归、分而治之、动态规划、回溯法和分支定界法等。

要对数据结构和算法设计方法给予评价，就必须能够计算程序性能。

数据结构和算法的关系

数据结构(data structures) + 算法(algorithms) = 程序(programs)
(data structures + algorithms) x efficiency = computation

程序性能分析

是指分析一个程序对于内存空间和运行时间的需求。

空间复杂度

指程序运行时临时占用内存的大小。广义上的概念是包括存储算法本身所占用的空间、算法的输入输出数据所占用的空间以及算法在运行过程中临时占用的存储空间这三个方面。

时间复杂度

指运行程序所需要的时间。这里度量的是程序中基本操作执行的次数，它是问题规模n的函数f(n)。记T(n)=O(f(n))，它表示随问题规模n的增大，算法执行时间的增长率和f(n)相同，称作算法的渐进时间复杂度。

复杂度分析

这里的复杂度分析通常指的是最坏时间复杂度分析。

常数阶O(1)

取前三个元素x = S[0]、y = S[1]和z = S[2]，这一步只需执行三次（从特定单元读取元素的）基本操作，耗费O(3)时间。接下来，为确定这三个元素的大小次序，最多需要做三次比较，也需O(3)时间。最后，输出居中的非极端元素只需O(1)时间。因此，上面取非极端元素算法的时间复杂度为：
T(n) = O(3) + O(3) + O(1) = O(7) = O(1)。

对数阶O(logn)

根据右移运算的性质，每右移一位，n都至少缩减一半。也就是说，至多经过1 + log2n次循环，n必然缩减至0，从而算法终止。因此时间复杂度为：O(1 + log2n) = O(log2n) 。

线性阶O(n)

平方阶O(n)

时间复杂度为：O(2n^2 + n + 1) = O(n^2)。

常见的算法时间复杂度排序

Ο(1) ＜ Ο(logn) ＜ Ο(n) ＜ Ο(nlogn) ＜ Ο(n^2) ＜ … ＜ Ο(2^n) ＜ Ο(n!)