算法 + 数据结构 = 程序

大纲

1. 逻辑结构

• 线性表、栈和队列、字符串（2-4章）
• 二叉树、树、图（5-7章）

1. 运算

• 内排序、文件管理、外排序（8-9章）
• 检索、索引（9-11章）

1. 高级数据结构（12章）

demo-农夫过河-最短路径模型: 好像是说用图来解决，图是二进制的，貌似好多疑难问题都可以到二进制上找到方法，二进制真神！

数据结构

1. 数据结构：逻辑、存储、运算

• 按照逻辑关系组织数据
• 按照一定的存储方法把它存储在计算机
• 在这些数据上定义一个运算的集合

1. 数据结构的逻辑组织

• 线性结构：线性表（表、栈、队列、串等）
• 非线性结构：数（二叉树、Huffman树、二叉检索树等）、图（有向图、无向图等）

算法

• 算法的渐进分析

f(n) = n² + 100n + ㏒10(n) + 1000

这里的时间复杂度就是取n的平方，因为随着n的逐步增大，其他项可以忽略不计

• 大O表示法，表示上限；上限和下限相同时，用大Θ

• 加法规则：f1(n) + f2(n) = max(f1(n) ,f2(n))，适用于顺序结构，比如if，switch

• 乘法规则：f1(n) * f2(n) = O(f1(n) * f2(n))，适用于循环结构，两层for循环，就是n的平方

• 大Ω表示法：关心的是算法的下界

• 增长率函数曲线：2^n > n^2 > nlog2n > n > log2n > O(1)

• 很多时候要考虑最坏、最好、平均的情况，比如利用if判断最好的情况，做一些特殊处理（比如提前return），压力测试就是考虑最坏的情况，通常考虑空间和cpu等是否会爆掉

• 正常从头到尾在数组中找k值，最好的情况是第一个就是，那就是O(1)，最坏是最后一个，那就是O(n)，平均是n+1/2，忽略常数项，就是O(n)；而二分法找，则是O(log(n))

• 大O、大Θ、大Ω也可以表示空间，这里的空间是指为了结果，运算中产生的辅助用的临时空间

• 很多时候，增加空间开销，可以改善算法的时间开销；节省空间，则需要增大运算时间，所以需要时空权衡，不过空间很多时候不怎么考虑，呵呵，除了大数据，比如音视频，图文

• 算法要酌情选择，比如O(n)，通常是还不错的，但是对搜索引擎，n是几百亿的网页，那么O(n)也不行，需要进行特殊的索引和检索处理，降到比如O(1)