- Categories · 计算机科学-

2022

本文深入浅出地介绍了计算机科学中至关重要的数据结构——树。从查找、插入和删除操作的效率提升动机出发,详细定义了树及其相关术语(如节点、边、根、叶子、父子关系)。重点阐述了二叉树的概念,并通过数学公式推导了满二叉树中节点数与深度的关系,揭示了树形结构实现 $O(\log n)$ 时间复杂度操作的潜力,为后续学习高级树形算法奠定了坚实基础。

2021

本文详细介绍了快速排序(Quick Sort)算法的原理,包括基准值选择策略、原位划分过程,并深入分析了其在最好、最坏及平均情况下的时空复杂度($O(n \log n)$ 至 $O(n^2)$),最后提供了 Java 和 C 语言的代码实现示例。

本文详细介绍了插入排序(Insertion Sort)算法的原理、伪代码、时空复杂度分析,并提供了 Java 和 C 语言的实现代码。插入排序在小规模数据或部分有序数据上表现优异。

2020

本文详细介绍了经典的选择排序算法(Selection Sort)。包括其工作原理(寻找最小元素并交换)、图解演示、伪代码、性能分析($O(n^2)$ 时间复杂度,不稳定),以及 Java 代码实现,重点探讨了其不稳定性及原因。

本文全面解析了线性搜索和二分搜索两种基础且核心的搜索算法。通过伪代码、示例和 Java 代码实现,详细阐述了它们的工作原理,并对比了 $O(n)$ 与 $O(\log n)$ 的时间复杂度差异,特别探讨了二分搜索中防止整型溢出的技巧,以及在 Java 中使用标准库进行高效搜索的最佳实践。

本文深入探讨操作系统的文件系统概念,详细解析文件与目录的结构(树状与无环图)、文件控制块(FCB)与打开文件表(OFT)的实现机制,并对比分析邻近、链式、簇式等磁盘块分配方案的优缺点。

2019

算法分析导论 2019-10-20

本文介绍了算法的基本概念、分类(确定性、随机、优化、并行、分布式)以及算法分析的核心指标(时间、空间、功耗等)。通过列表操作的例子,形象地解释了算法效率的差异。