**************************************** 数据结构和算法分析 **************************************** :bilibili: https://gitee.com/luzhenxiong/bilibili-leetcode :视频里程碑: https://www.bilibili.com/video/BV1tU411U7SF 介绍 ====================================================== :算法: 是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令, 算法代表着用系统的方法描述解决问题的策略机制。 :数据结构: 计算机存储、组织数据的方式。希望算法解决问题的效率越快越好，于是我们就需要考虑数据究竟如何保存的问题。 逻辑结构分类 ---------------------------------------------- 逻辑结构是从具体问题中抽象出来的模型，是抽象意义上的结构，按照对象中数据元素之间的相互关系分类 * 集合结构: 数据元素除了同一个集合外，他们之间没有任何其他的关系。 * 线性结构: 数据元素之间存在一对一的关系 * 树形结构: 数据元素之间存在一对多的层次关系 * 图形结构: 数据元素是多对多的关系 物理结构 -------------------------------- 逻辑结构在计算机中真正的表示方式(又称为映像)称为物理结构，也可以叫做存储结构。 顺序存储结构 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的，比如数组就是顺序存储结构。 链式存储结构 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 是把数据元素存放在任意的存储单元里面, 这组存储单元可以是连续的也可以是不连续的。此时，数据元素之间并不能反映元素间的逻辑关系，因此链式存储结构中引进 了一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置 线性结构和非线性结构 --------------------------------------- **线性结构** * 数组 * 队列 * 链表 * 栈 **非线性结构** * 二维数组 * 多维数组 * 广义表 * 树结构 * 图结构 估计算法运行效率与时间复杂度 ====================================================== * 时间复杂度 - 在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。 * 空间复杂度 - 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。 对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。 算法的时间复杂度和空间复杂度合称为算法的复杂度。数量级常被称作大O记法(O指order)，记作O(f(n))。 常见的大O函数 * 常数级别-1: 普通语句(将两个数相加) * 对数级别-logN: 二分策略(二分查找) * 线性级别-N: 循环(找出最大元素) * 线性对数级别-NlogN: 分治思想(归并排序) * 平方级别-N^2: 双层循环(检查所有元素对) * 立方级别-N^3: 三层循环(检查所有三元组) * 指数级别-2^N: 穷举查找(检查所有子集) 常见的时间复杂度 O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^2logn) < O(n^3) 复杂问题的时间复杂度 O(n!) O(2^n) O(n^n) .. tip:: 快速判断算法复杂度, 适用于绝大多数简单情况: * 确定问题规模n * 循环减半过程 -> logN * k层关于n的循环 -> n^k 常数级别 -------------------------- .. code-block:: python print("Hello World") 线性级别 --------------------------- .. code-block:: python n: int for i in range(n): print('Hello World') 平方级别 ------------------------------- .. code-block:: python for i in range(n): for j in range(n): print('Hello World') 立方级别 ------------------------------- .. code-block:: python for i in range(n): for j in range(n): for i in range(n): print('Hello World') 对数级别 ---------------------------- 当算法过程出现循环折半的时候，时间复杂度式子中会出现logn .. code-block:: python while n > 1: print(n) n = n // 2 空间复杂度 ===================================== 表示方式与时间复杂度完全一样 * 算法使用了几个变量: O(1) * 算法使用了长度为n的一维列表: O(n) * 算法使用了m行n列的二维列表: O(mn) 时间比空间重要，现在机器和硬件便宜 排序算法 ========================================== 基数排序 ------------------------------------ 基数排序(radix sort)属于"分配式排序" (distribution sort), 又称"桶子法"，思想是将整数按位数切割成不同的数字，然后按每个位数分别比较。 基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。 LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。 思想 ~~~~~~~~~~~~~~~~~~~~~~~~~~~ 将所有的待比较数值统一设置位同样的数位长度，位数比较短的数前面补零，然后从最低位开始依次进行一次排序，这样从最低位排序一直到最高位排序完成后，数列就变成一个有序序列 例如, 数组[53, 3, 542, 728, 14, 214] 1. 首先确定最大数是728(这个一定要确定, 通过循环数组找出来) 2. 确定位数后，不足十位和百位的在前面补0 3. 比较数组中的个位数, 按照顺序放到对应的桶中，每个桶都是一个一维数组，全部放进去后，再取出来重新排序。(得到542, 53, 3, 14, 214, 728) 4. 然后再依次比较十位数，放到对应的桶中，没有十位的前面补0。(得到3, 14, 728, 542, 53) 5. 依次比较百位数，放到对应的桶中，没有百位的补0。(得到3, 14, 53, 214, 542, 728) 冒泡排序 ------------------------------------------ 冒泡排序多次遍历列表。它比较相邻的元素，将不合顺序的交换。每一轮遍历都将下一个最大值放到正确的位置上。 快速排序 ------------------------------------------ 对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分所有的数据都要小，然后再按此方法对这两部分数据分 别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 递归 ====================================================== .. toctree:: :maxdepth: 2 :caption: 参考资料 详解递归 递归 动态规划的本质 **递归三原则** * 递归算法必须有基本情况(算法停止递归的条件); * 递归算法必须改变其状态并向基本情况靠近; * 递归算法必须递归地调用自己; 为了遵守第二条原则，必须设法改变算法的状态，从而使其向基本情况靠近。 丑数 =================================================== 把只包含质因子2，3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。 习惯上我们把1当做是第一个丑数。 .. code-block:: python assert 6 % 2 == 0 assert 7 % 2 != 0 assert 7 % 3 != 0 assert 7 % 5 != 0 递归 ======================== 动态规划 ------------------ :核心思想: 记住已有的结果，减少计算量。简单的做法是把计算结果存储在一张表中，并在计算新的结果之前，检查结果是否已在表中。如果是，就直接使用，而不是重新计算。 :经典问题: 找零时使用最少的硬币