《算法导论》学习笔记：基础知识与算法入门

具有数字索引的全局变量。 第 3 章：函数的增长 1. 渐进符号是一种描述算法运行时间的方式，一般分为三种：大 O符号、ΩOmega符号和ΘTheta符号。 2. 大 O符号表示算法的运行时间上界，ΩOmega符号表示算法的运行时间下界，ΘTheta符号表示算法的运行时间上下界。 3. 渐进符号在算法分析中非常重要，可以帮助我们估计算法的效率和性能。 第二部分：排序和顺序统计 第 4 章：分治法 1. 分治法是一种求解问题的思想，它将问题分为更小的子问题，然后递归地求解子问题，最后将子问题的解合并起来，得到原问题的解。 2. 分治法的复杂度往往比较高，但如果能够设计合适的子问题，会大大提高算法的效率。 第 5 章：堆排序 1. 堆是一种特殊的树形数据结构，它具有以下性质： 1. 结构性质：堆是一颗完全二叉树。 2. 堆序性质：对于每个节点i，有heap[parent(i)] ≥ heap[i]，即父节点的值大于等于子节点的值。 2. 堆排序利用堆的性质来进行排序，它的平均时间复杂度为O(nlogn)。 第 6 章：快速排序 1. 快速排序是一种常用的排序算法，它利用分治法和递归的思想，通过将数组分成两个子数组来排序。 2. 快速排序的平均时间复杂度也为O(nlogn)，但是它的最坏时间复杂度为O(n^2)，需要特别注意。 第 7 章：线性时间排序 1. 线性时间排序是指能在O(n)时间内完成的排序算法，其中包括计数排序、基数排序和桶排序等。 2. 这些排序算法的特点是算法的时间复杂度与输入规模成线性关系，可以在特定情况下大大提高排序的效率。 第三部分：数据结构 第 8 章：基本数据结构 1. 基本数据结构包括数组、链表、栈、队列和树等，它们是算法设计的基础。 2. 不同的数据结构适用于不同的问题，选择合适的数据结构可以提高算法的效率。 第 9 章：散列表 1. 散列表是一种用来实现关联数组的数据结构，它能够在平均情况下提供O(1)时间复杂度的查找、插入和删除操作。 2. 散列表的性能往往受到哈希函数和冲突处理方法的影响，需要合理设计才能发挥其优势。 第 10 章：二叉搜索树 1. 二叉搜索树是一种具有良好性能的数据结构，它的查找、插入和删除操作的时间复杂度都为O(logn)。 2. 但是在最坏的情况下，二叉搜索树可能退化成链表，使得时间复杂度上升至O(n)，需要注意其平衡性。 第 11 章：红黑树 1. 红黑树是一种自平衡的二叉搜索树，它通过引入约束条件，保证了树的平衡性，使得其查找、插入和删除操作的时间复杂度都为O(logn)。 2. 红黑树的平衡性能够较好地保持，是一种常用的数据结构。 第四部分：高级设计和分析技术 第 12 章：贪心算法 1. 贪心算法是一种常用的算法思想，它每次都选择当前看起来最好的选择，希望最终能够得到全局最优解。 2. 贪心算法的适用范围比较广泛，但需要合理设计问题的模型和选择适当的贪心策略。 第 13 章：动态规划 1. 动态规划是一种通过子问题的解求解原问题的方法，它具有以下特点： 1. 最优子结构：原问题的最优解可以由子问题的最优解推导而来。 2. 重叠子问题：子问题之间有重叠。 2. 动态规划可以用来解决具有重叠子问题和最优子结构性质的问题，如矩阵链乘法、最长公共子序列和背包问题等。 "