数据结构和算法分析
- bilibili:
- 视频里程碑:
介绍
- 算法:
是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令, 算法代表着用系统的方法描述解决问题的策略机制。
- 数据结构:
计算机存储、组织数据的方式。希望算法解决问题的效率越快越好，于是我们就需要考虑数据究竟如何保存的问题。
逻辑结构分类
逻辑结构是从具体问题中抽象出来的模型，是抽象意义上的结构，按照对象中数据元素之间的相互关系分类
集合结构: 数据元素除了同一个集合外，他们之间没有任何其他的关系。
线性结构: 数据元素之间存在一对一的关系
树形结构: 数据元素之间存在一对多的层次关系
图形结构: 数据元素是多对多的关系
物理结构
逻辑结构在计算机中真正的表示方式(又称为映像)称为物理结构，也可以叫做存储结构。
顺序存储结构
把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的，比如数组就是顺序存储结构。
链式存储结构
是把数据元素存放在任意的存储单元里面, 这组存储单元可以是连续的也可以是不连续的。此时，数据元素之间并不能反映元素间的逻辑关系，因此链式存储结构中引进 了一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置
线性结构和非线性结构
线性结构
数组
队列
链表
栈
非线性结构
二维数组
多维数组
广义表
树结构
图结构
估计算法运行效率与时间复杂度
时间复杂度 - 在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。
空间复杂度 - 空间复杂度(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)
小技巧
快速判断算法复杂度, 适用于绝大多数简单情况:
确定问题规模n
循环减半过程 -> logN
k层关于n的循环 -> n^k
常数级别
print("Hello World")
线性级别
n: int
for i in range(n):
print('Hello World')
平方级别
for i in range(n):
for j in range(n):
print('Hello World')
立方级别
for i in range(n):
for j in range(n):
for i in range(n):
print('Hello World')
对数级别
当算法过程出现循环折半的时候，时间复杂度式子中会出现logn
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]
首先确定最大数是728(这个一定要确定, 通过循环数组找出来)
确定位数后，不足十位和百位的在前面补0
比较数组中的个位数, 按照顺序放到对应的桶中，每个桶都是一个一维数组，全部放进去后，再取出来重新排序。(得到542, 53, 3, 14, 214, 728)
然后再依次比较十位数，放到对应的桶中，没有十位的前面补0。(得到3, 14, 728, 542, 53)
依次比较百位数，放到对应的桶中，没有百位的补0。(得到3, 14, 53, 214, 542, 728)
冒泡排序
冒泡排序多次遍历列表。它比较相邻的元素，将不合顺序的交换。每一轮遍历都将下一个最大值放到正确的位置上。
快速排序
对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分所有的数据都要小，然后再按此方法对这两部分数据分 别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
递归
递归三原则
递归算法必须有基本情况(算法停止递归的条件);
递归算法必须改变其状态并向基本情况靠近;
递归算法必须递归地调用自己;
为了遵守第二条原则，必须设法改变算法的状态，从而使其向基本情况靠近。
丑数
把只包含质因子2，3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但7、14不是，因为它们包含质因子7。 习惯上我们把1当做是第一个丑数。
assert 6 % 2 == 0
assert 7 % 2 != 0
assert 7 % 3 != 0
assert 7 % 5 != 0
递归
动态规划
- 核心思想:
记住已有的结果，减少计算量。简单的做法是把计算结果存储在一张表中，并在计算新的结果之前，检查结果是否已在表中。如果是，就直接使用，而不是重新计算。
- 经典问题:
找零时使用最少的硬币