前言学习数据结构与算法先要分清两个问题数据怎样组织操作怎样完成。前者由数据结构解决后者由算法解决。写代码时除了得到正确结果还要关注程序执行要花多少时间、占多少额外空间。数据结构和算法是什么数据结构是数据在计算机中的组织方式。它既包含数据之间的逻辑关系也包含具体的存储方式。从逻辑结构看常见的类型有集合结构、线性结构、树形结构和图状结构。例如数组和链表属于线性结构二叉树属于树形结构。从存储方式看数据可以连续存放也可以离散存放顺序存储元素放在连续的存储空间中例如数组。非顺序存储元素分散存放通过关系把它们连接起来包括链式存储、索引存储和散列存储。算法是解决某类问题的一组有限步骤。一个算法需要具备确定性相同的输入应得到相同的输出它也必须在有限步骤后结束。评价算法时除了正确性、可读性和健壮性还要看运行效率和存储需求。时间复杂度时间复杂度用来描述当数据规模 n 增大时算法执行次数增长得有多快。它通常写成O( )关注增长趋势不统计某一台电脑上的实际秒数。计算规则多项式相加只保留最高阶系数化为 1。例如T(n) 3n² 5n 10当 n 很大时n² 的增长最快因此时间复杂度为O(n²)。嵌套循环复杂度相乘。for(inti0;in;i){for(intj0;jn;j){// 执行一次常量操作}}外层循环执行 n 次内层每次执行 n 次总执行次数约为 n × n所以时间复杂度是O(n²)。顺序执行的代码复杂度相加后再取最高阶。for(inti0;in;i){// O(n)}for(intj0;jn*n;j){// O(n²)}总复杂度为 O(n n²)保留最高阶后是O(n²)。常见时间复杂度从低到高可以简单记为O(1)、O(log n)、O(n)、O(n log n)、O(n²)。在数据量较大时增长级别的差异会非常明显。空间复杂度空间复杂度描述算法运行时额外申请的存储空间随 n 的增长情况。这里主要看辅助变量、数组、递归调用等产生的额外空间不把输入数据本身重复计算进去。计算规则固定数量的变量占用常量空间。intmax0;intindex0;无论 n 多大变量数量都不变空间复杂度为O(1)。申请长度和 n 成正比的数组空间复杂度为 O(n)。int[]tempnewint[n];数组长度随 n 一起增长因此额外空间为O(n)。二维数组的行和列都与 n 有关空间复杂度为 O(n²)。int[][]matrixnewint[n][n];它一共保存 n × n 个元素因此空间复杂度为O(n²)。循环次数多不一定占用更多空间。只要循环中没有持续申请与 n 相关的新空间即使时间复杂度是 O(n²)空间复杂度也可能仍是 O(1)。总结数据结构决定数据怎样存放算法决定问题怎样求解。分析复杂度时时间复杂度看操作次数的增长空间复杂度看额外存储量的增长。掌握“取最高阶”和“嵌套相乘”这两条规则就能完成大多数基础复杂度判断。
