[数据结构与算法]2021-08-31 数据结构与算法 NO.1

first：概念

数据结构：

? ? ? ? 存储结构：顺序存储-连续

? ? ? ? ? ? ? ? ? ? ? ? ? 非顺序存储-离散

算法：

? ? ? ? 特性：有穷性，确定性，可行性，输入，输出

? ? ? ? 特质：正确性，可读性，健壮性，高效率与低存储量要求（时间复杂度和空间复杂度低）

? ? ? ? 时间复杂度：计算方法：找到最深层循环——分析该基本操作的执行层次数x与问题规模n的关系 x=f(n)——x的数量级O(x)就是时间复杂度

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 常用技巧：加法规则：O(f(n))+O(g(n))=O(max(f(n),g(n)))

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 乘法规则：O(f(n))xO(g(n))=O(f(n)xg(n))

? ? ? ? 空间复杂度：找到所占空间大小与问题规模相关变量——分析所占空间下、与问题规模n的关系x=f(n)——x的数量级O(x)就是空间复杂度S(n)

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 常用技巧：加法规则：O(f(n))+O(g(n))=O(max(f(n),g(n)))

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 乘法规则：O(f(n))xO(g(n))=O(f(n)xg(n))