第八周作业总结

数据结构与算法

时间复杂度和空间复杂度

算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。



时间复杂度

并不是计算程序具体运行的时间，而是算法执行语句的次数

时间复杂度常用大 O 符号表述，一般不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷（n 表示）时的情况。



空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，O(n）表示需要临时存储N个数据。



数据结构

数组：线性表的一种，一块连续的内存区，因此元素的访问时间复杂度是 O(1)，但是插入数据和删除数据操作复杂，还有越界的风险。



链表：也是线性表，但在内存中是分散的，访问时间复杂度是 O(n)，插入数据和删除数据操作简便，而且链表长度几乎没有限制（不超过内存空间的情况下）



Hash 表：哈希表是根据键（Key）而直接访问在内存储存位置的数据结构。它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，从而加速了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。



栈：也是一种线性表结构，实现上可以是数组也可以是链表。它规定了数据存取的规则后进先出——被插入的数据会放到线性表头部，读取时也是从线性表的头部开始。



队列：队列的实现结构和栈一样，但是它的存取规则是先进先出——被插入的数据被放到线性表尾部，而读取的时候总是从线性表的头部开始。



树：是一种抽象数据类型，用来模拟具有树状结构性质的数据集合。它是由 n 个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。



二叉查找树（BST）：运用了二分查找的思想，查找所需的最大次数等于树的高度；但是有缺点：可能会成为单边的二叉树，搜索时间复杂度为 O(n)



平衡二叉树（AVL）：是对 BST 的改进，任一节点对应的两棵子树的最大高度差为 1；但是为了自平衡，插入数据时需要不断自旋调整，效率较低



红黑树：上面两数的 trade-off，自平衡的二叉查找树，能保证根到叶子的最长路劲不会超过最短路径的 2 倍；又能在插入数据时，保证最多只需 3 次旋转即能平衡



B+树：通常用于数据库和操作系统的文件系统中。B+树中的节点通常被表示为一组有序的元素和子指针；因此它是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。



跳表：是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。



算法

递归：是指一种通过重复将问题分解为同类的子问题而解决问题的方法。常用来解决的问题有：



数据的定义是按递归定义的。如费氏数列。

问题解法按递归算法实现。如汉诺塔。

数据的结构形式是按递归定义的。如二叉树、广义表等。

贪心：是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。对于大部分的问题，贪心法通常都不能找出最佳解，因为他们一般没有测试所有可能的解。贪心法容易过早做决定，因而没法达到最佳解。不过也有例外，在某些图论上可以得到最优解，如著名的 Prim 算法、Kruskal 算法均为贪心算法。



动态规划：通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。著名的动态规划算法有：最长公共子序列、Floyd-Warshall 算法、Viterbi 算法等等。



遗传算法：最初是借鉴了进化生物学中的一些现象而发展起来的搜索算法，这些现象包括遗传、突变、自然选择以及杂交等等。遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）可抽象表示为染色体，使种群向更好的解进化。遗传算法擅长解决的问题是全局最优化问题，例如，解决时间表安排问题就是它的一个特长，很多安排时间表的软件都使用遗传算法，遗传算法还经常被用于解决实际工程问题。



网络通信

OSI 七层模型 v.s. TCP/IP 四层模型

网络传输控制协议有两种最基本的模型——OSI 和 TCP/IP 协议。如图所示：两者都是标准模型，相比之下 OSI 更为严谨详实；但是经过多年斗争，TCP/IP 胜出，因为简单粗暴才更能被广泛应用。