Uwakeme

一、贪婪算法概述贪婪算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法。贪婪算法不从整体最优上加以考虑，它所做出的选择只是在某种意义上的局部最优选择。 （一）算法适用场景贪婪算法适用于具有”贪心选择性质”的问题，即局部最优选择能导致全局最优解的问题。主要应用于： 需要求解最优化问题 问题具有贪心选择性质 问题具有最优子结构性质 （二）算法基本特点 简单直接：思路简单，容易实现 局部最优选择：每步都选择当前看起来最优的解 不可回退：一旦做出选择，不再更改 不保证全局最优：在某些问题上可能无法得到全局最优解 二、算法步骤详解（一）算法流程贪婪算法的一般流程如下： 建立数学模型，定义最优化目标 将问题分解为若干个子问题 对每个子问题做出贪心选择（局部最优） 将贪心选择合并成最终解决方案 （二）图示说明贪婪算法通常按照以下流程执行： 创建一个空结果集 按照某种顺序遍历所有可能的选择 对于每个选择，检查是否可以加入结果集 如果可以，则加入结果集 重复步骤2-4，直到问题解决 三、经典贪婪算法问题（一...

前言《算法图解》的最后一章”接下来如何做”（Where to Go from Here）是作者对读者进一步学习算法和编程的指引。在前面的章节中，我们已经学习了许多基础而重要的算法，从二分查找、快速排序到广度优先搜索、迪杰斯特拉算法，再到动态规划、K近邻算法等。现在，是时候思考如何继续深入学习，拓展我们的算法知识体系了。本笔记将总结第十三章的核心内容，并补充一些个人的学习建议和资源推荐。 一、后续学习的算法和数据结构原书在最后一章提到了几个值得进一步学习的高级算法和数据结构，下面对它们进行简要介绍。 （一）树相关算法与数据结构《算法图解》在前面的章节已经介绍过二叉树和二叉搜索树的基本概念。作者建议进一步学习更高级的树结构： 红黑树：一种自平衡的二叉搜索树，通过颜色标记和特定规则保持平衡，保证操作的时间复杂度为O(log n) B树：为磁盘等外部存储设计的多路搜索树，能够有效减少I/O操作 堆（Heap）：一种特殊的完全二叉树，常用于实现优先队列 伸展树（Splay Tree）：一种自调整的二叉搜索树，会将最近访问的节点移动到根部，提高后续访问的效率 这些树结构在各种系...

前言《算法图解》第十二章介绍了一种简单而强大的机器学习算法——K近邻算法（K-Nearest Neighbors，简称KNN）。这是一种基于实例的学习方法，也是机器学习领域中最基础、最直观的算法之一。本章不仅讲解了KNN的基本原理和实现方式，还探讨了特征提取、归一化等重要概念，为读者打开了机器学习的大门。本笔记将梳理KNN算法的核心思想、实现步骤以及应用场景。 一、K近邻算法概述（一）基本思想K近邻算法的核心思想非常简单：物以类聚，人以群分。它基于一个假设：相似的事物通常具有相似的特征，并且在特征空间中彼此靠近。 具体来说，KNN算法的基本思路是： 对于一个待分类的新实例，在训练数据集中找到与它最相似（距离最近）的K个实例 这K个实例中出现最多的类别，就作为新实例的预测类别 （二）算法特点KNN算法具有以下特点： 非参数化方法：不对数据分布做任何假设，完全依赖于数据本身 惰性学习：没有显式的训练过程，只在需要预测时才进行计算 直观易懂：算法思想简单，容易理解和实现 计算复杂度高：预测时需要计算新实例与所有训练实例的距离 二、KNN算法步骤详解（一）算法流程KNN算法的基本...

前言《算法图解》第四章引入了一种强大的算法设计策略——分而治之 (Divide and Conquer, D&C)。这种策略将复杂问题分解为更小、更易于管理的部分，然后递归地解决这些部分，最终合并结果。作为 D&C 策略的经典应用，本章详细介绍了快速排序 (Quicksort) 算法，它是一种非常高效且广泛使用的排序方法。本笔记将梳理 D&C 的核心思想以及快速排序的实现原理与性能分析。 一、分而治之 (Divide and Conquer, D&C)分而治之是一种解决问题的范式，其核心思想是将一个难以直接解决的大问题，分割成一些规模较小的相同或相似的子问题，以便各个击破，分而治之。 （一）D&C 的工作原理使用 D&C 解决问题通常包含以下两个步骤： **找出基线条件 (Base Case)**：确定问题可以被分解到的最小规模，这种规模的问题可以直接解决，无需进一步分解。这是递归的出口。 **分解与递归 (Divide & Recur)**：描述如何将问题分解成更小的子问题，以及如何递归地解决这些子问题，直到达到基线条件...

前言在上一章中，我们学习了二叉搜索树(BST)的基本概念和操作。虽然BST在平均情况下提供了O(log n)的搜索、插入和删除效率，但在最坏情况下（如按顺序插入数据），它可能退化为链表，导致操作效率降为O(n)。为了解决这个问题，《算法图解》第八章介绍了平衡树的概念和几种主要的平衡树结构，这些结构能够在各种情况下保持较好的平衡性，确保操作的高效性。 一、平衡树的基本概念（一）什么是平衡树平衡树是一种特殊的二叉搜索树，它通过某些机制来保持树的平衡，避免树向一侧过度生长。所谓”平衡”，通常是指树的左右子树高度大致相同，或者满足某些特定的平衡条件。 平衡树的目标是确保树的高度接近于log n（其中n是节点数），这样可以保证基本操作（查找、插入、删除）的时间复杂度为O(log n)，即使在最坏情况下也是如此。 （二）为什么需要平衡树回顾上一章中提到的问题：当按顺序（如升序或降序）向BST中插入数据时，树会变得极度不平衡，形成一个链表状结构： 1234567891 \ 2 \ 3 \ 4 \ 5 在这种情况下，查找、插入和删除操作的...

前言《算法图解》第六章为我们介绍了一种基础且强大的图搜索算法——**广度优先搜索 (Breadth-First Search, BFS)**。这种算法能够系统地探索图中的节点，常用于解决两类核心问题：一是判断从一个节点到另一个节点是否存在路径；二是在无权图中找到两个节点之间的最短路径。本笔记将深入探讨图的基本概念、BFS 的工作原理、其实现方式以及相关的性能分析。 一、图（Graph）简介在讨论 BFS 之前，我们需要理解什么是图。 （一）什么是图图是一种由节点 (Nodes 或 Vertices) 和连接这些节点的边 (Edges) 组成的数据结构。图用于表示各种实体之间的关系。 节点：代表图中的事物或点。例如，在社交网络中，节点可以代表人；在地图中，节点可以代表城市。 边：代表节点之间的连接或关系。例如，在社交网络中，边可以表示朋友关系；在地图中，边可以表示城市间的道路。 （二）有向图与无向图 **有向图 (Directed Graph)**：图中的边具有方向性。如果存在一条从节点 A 指向节点 B 的边，意味着关系是从 A 到 B，但不一定是从 B 到 A。例如，Twi...

一、动态规划概述动态规划（Dynamic Programming，简称DP）是一种通过将复杂问题分解为更简单的子问题来解决问题的方法。它是一种强大的算法设计技术，特别适用于具有重叠子问题和最优子结构性质的问题。 （一）算法适用场景动态规划主要适用于以下场景： 最优化问题（求最大值、最小值） 计数问题（求方案数） 具有重叠子问题特性的问题 具有最优子结构特性的问题 （二）算法基本思想动态规划的核心思想是： 将原问题分解为相互依赖的子问题 求解每个子问题仅一次，并将结果存储在表格中 自底向上地构建解决方案 通过组合子问题的解来得到原问题的解 二、动态规划的关键要素（一）最优子结构如果问题的最优解包含其子问题的最优解，则该问题具有最优子结构性质。这是应用动态规划的必要条件。 例如，最短路径问题具有最优子结构：如果从A到C的最短路径经过B，那么A到B的这段路径一定是A到B的最短路径。 （二）重叠子问题当问题的递归算法会重复计算相同的子问题时，我们称该问题具有重叠子问题特性。动态规划通过存储已解决的子问题的结果来避免重复计算。 例如，计算斐波那契数列时，递归算法会重复计算相同的子问...

前言《算法图解》(Grokking Algorithms) 是由 Aditya Y. Bhargava 编写的一本算法入门书籍，以其通俗易懂的语言和生动形象的图解闻名。本书特别适合算法初学者，通过简明的解释和丰富的插图，将复杂的算法概念转化为易于理解的内容。笔者通过系统学习这本书，记录了各章节的学习笔记，本文作为总结和导航，帮助读者快速了解全书内容并方便查阅各章节的详细笔记。 一、《算法图解》整体内容概述《算法图解》从基础的算法概念开始，逐步深入到更复杂的算法思想，全书共13章，涵盖了以下核心内容： （一）基础算法与数据结构 二分查找：一种针对有序数组的高效查找算法，时间复杂度为O(log n) 数组与链表：两种基本数据结构，各有优缺点 递归：一种解决问题的重要思想，通过函数调用自身来解决问题 栈：一种后进先出(LIFO)的数据结构，用于实现递归 **散列表(哈希表)**：通过键值对实现快速查找的数据结构 （二）排序算法 选择排序：一种简单直观的排序算法，时间复杂度为O(n²) 快速排序：一种高效的分治排序算法，平均时间复杂度为O(n log n) 归并排序：另一种分治排序算法...

前言《算法图解》是一本入门算法的优秀读物，以图文并茂的方式讲解了各种基础算法。笔者最近在学习此书，特此记录学习笔记。本篇笔记主要记录第一章的核心内容，包括什么是算法、二分查找的思想及其实现、以及衡量算法效率的大O表示法。 一、什么是算法算法（Algorithm）是一组用于完成特定任务的指令。简单来说，就是解决问题的方法和步骤。一个好的算法，不仅要能够正确解决问题，还要追求更高的效率，即用更少的时间和更少的内存。 二、二分查找二分查找（Binary Search）是一种高效的查找算法，但它有一个重要的前提：输入的数据必须是有序的。 （一）算法原理二分查找的原理非常简单。想象一下在电话簿里找一个名字，或者在字典里查一个单词。我们通常不会从第一页开始逐个查找，而是会： 打开书大约中间的一页。 比较中间的条目与我们要查找的目标。 如果目标条目在当前条目的前面，则在书的前半部分重复此过程。 如果目标条目在当前条目的后面，则在书的后半部分重复此过程。 重复以上步骤，直到找到目标或确定目标不存在。 这个过程就是二分查找。每次查找都将搜索范围缩小一半，因此效率很高。 例如，在一个包含 100...

前言在前面的章节中，我们学习了数组、链表、散列表等基本数据结构，以及一些基础算法。本章将介绍一种非常重要的数据结构——树(Tree)，特别是二叉搜索树(Binary Search Tree)。树结构在计算机科学中应用广泛，从文件系统到数据库再到人工智能，都能看到树的身影。《算法图解》第七章深入浅出地介绍了树的基本概念、实现和应用，帮助读者理解这一关键数据结构。 一、树的基本概念（一）什么是树树是一种分层数据的抽象模型，它由一系列节点组成，这些节点通过边相连。树具有以下特性： 树有一个根节点(Root)，它是树的起始点 除根节点外，每个节点都有且仅有一个父节点 每个节点可以有零个或多个子节点 节点之间没有循环连接（这意味着树是无环的） 没有子节点的节点称为叶节点(Leaf) 树的常见术语： 节点(Node): 树中的基本单位，包含数据和指向其他节点的链接 边(Edge): 连接两个节点的线 根(Root): 树顶部的节点，是树中唯一没有父节点的节点 叶节点(Leaf): 没有子节点的节点 父节点(Parent): 有子节点的节点 子节点(Child): 有父节点的节点 兄弟节...