算法学习日志【七】：查找算法（三）
2025-04-29 360 字 2 分钟

算法学习日志【七】：查找算法（三）

散列表 通过红黑二叉查找树的实现，我们已经让查找算法足够高效，对于一个庞大的数据集，平衡二叉树和红黑树对于查找的时间复杂度已经达到了 $O(lgN)$ ；但是有没有一种更高效的查找算法，让时间复杂度降低到常数级别呢？答案是肯定的，试想一下，假如我们可以直接将想要查找的键作为符号表的索引，那么我们每次的查找都只需要在存放这种索引的符号表中直接对该索引保存的键值对进行引用就好了，这样每次查找的时间就可以压缩到接近常数级别。因此，我们需要一个函数，这个函数需要足够高效，可以通过简单的计算，将输入的键映射到数组的某一个索引中。该函数我们称之为散列函数。 散列函数 假设我们有一个大小为M的数组，那么我 …
算法学习日志【六】：查找算法（二）
2025-04-17 977 字 5 分钟

算法学习日志【六】：查找算法（二）

二叉查找树 定义：一颗二叉查找树是一颗二叉树，其中每个结点都含有一个Comparable的键和一个相关联的值，且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的键 当我们拥有了这样一棵二叉查找树时，我们要查找一个键几句需要沿着这棵树向下比较每个结点的键和目标键的大小，最终只有两种可能出现的情况：即要么该键存在于表中，返回对应的值；要么查找该键不存在于表中，最终向下找到一个null值，则返回null。 特点： 运行时间取决于树的形状，即取决于键被插入的先后顺序； 最好的情况下，一个大小为N的树，从根结点到达底部结点需要经过lgN步（完全平衡）；最差则需要N步 在由 N 个随机 …
算法学习日志【五】：查找算法（一）
2025-04-15 597 字 3 分钟

算法学习日志【五】：查找算法（一）

大量、高效地检索信息是现代计算机和网络的一大特点，这些检索操作大都是由各种查找算法实现的，如果没有高效的查找算法，现代计算机更高级的功能也就无从谈起。 对于经典查找算法，我们需要建立一种新的抽象：符号表（或被称为字典），并且用三种数据类型来实现它：二叉查找树、红黑树和散列表。 符号表 一个基本的符号表包括键（Key）和对应的值（Value）。对于符号表来说，如果把符号表看作一个个小黑屋，“键”就好像是一个通往对应的“值”的窗口，检索、删除、查找等操作都是通过键来完成。一种简单的符号表API如下： 规则： 符号表不允许重复的键，但可以用不同的键来存储同一个值 键和值都不能为空 当值为空时，认为该 …
宅兹中国，炎帝故里——宝鸡
2025-04-06 13 字 1 分钟

宅兹中国，炎帝故里——宝鸡

一年前大一的时候就萌生了“寻找中华文脉”主题旅游路线的计划，碍于琐事与学业，这个计划迟迟没有开始。又因为这个学期的学业负担有所减弱，在为自己平淡乏味的大一生活感到扼腕叹息同时，终于能够开始行万里路、遍访文化发展之处。这篇博客纪念此行第一站：炎帝故里——宝鸡。 旅行随记 宝鸡的城市氛围很慢，但很和谐。路过一个公园看到大爷大妈们三五成群，或随性演奏，或相伴起舞，遂随手拍摄几张： 长乐塬抗战工业遗址 如果没有对抗战时期历史或相关遗迹有纯粹、强烈的兴趣与热爱的话不推荐去。50块钱的门票但是内容很少，应该是有很大一部分还在建造施工；一共三座一层的建筑，游览一圈用时不会超过2小时。 宝鸡有两条著名的古街， …
算法复习日志【四】：优先队列
2025-04-02 1041 字 5 分钟

算法复习日志【四】：优先队列

概述 优先队列不同于普通队列，优先队列不再仅遵循“先进先出”规则，当删除元素时，优先队列总是倾向于删除优先级最高的元素。其支持两种操作：删除最大元素和插入元素。 应用场景：模拟系统、任务调度、数值计算。 延拓：堆排序 范型优先队列API如下： 实现方法 总的来说，和排序算法类似，实现优先队列有数组和链表两种实现结构；每种数据结构实现又可以分别按照插入时保持队列有序和取出时找到最大元素两种思路进行设计。具体方法代码如下（以插入时保持队列有序的数组实现和取出最大元素的链表实现为例）： 插入时保持队列有序的数组实现： public class PQueueSortedArray<Key …
算法复习日志【三】：排序
2025-04-01 864 字 5 分钟

算法复习日志【三】：排序

初级排序算法 标准的排序算法应该有一个交换器exch()、一个比较器less()，并且需要有一个检验器isSorted()和一个打印器show()来验证数组是否完成排序。评价一个排序算法需要关注这个算法的运行时间和额外的内存使用情况。 // 比较器 private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } // 交换器 private static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; …
算法复习日志【二】：算法复杂度分析与Union-Find算法
2025-03-30 330 字 2 分钟

算法复习日志【二】：算法复杂度分析与Union-Find算法

算法复杂度分析 算法复杂度有时间和空间两种，每种都可用大$O$，大$\Theta$ ，大$\Omega$，小$o$，小$\omega$ 进行表示 大O表示法 大O表示法是我们在分析算法复杂度时最常用的一种表示法。 大O表示法全称为只可以表示函数运行时间和占据空间的上限，即用于描述算法的最坏复杂度。 关于大O表示法的更详细解读，参考这篇博客：图解大 O 表示法 大$\Omega$表示法 当函数的大小只有下界，没有明确的上界的时候，可以使用大Ω表示法，该渐进描述符一般用与描述算法的 最优复杂度 。 大$\Theta$表示法 如果一个函数 $f(N)$ 既是 $O(g(N))$ …
计算机系统学习日志【二】：信息的表示和处理
2025-03-29 9 字 1 分钟

计算机系统学习日志【二】：信息的表示和处理

每个计算机都有一个字长，字长决定虚拟地址空间的最大大小，对当前大多数64位计算机而言，虚拟地址空间最大为$2^{64}$个字节，即程序最多访问约为$1.6 \times 10^{19}$个字节。 假设一个int型的变量x的地址为0x100，那么x的四个字节将被存储在存储器的0x100, 0x101, 0x102, 0x103位置。 大端序：最高有效字节存储在最前面的位置 小端序：最低有效字节存储在最前面的位置
csapp学习日志【一】：计算机系统漫游
2025-03-29 38 字 1 分钟

csapp学习日志【一】：计算机系统漫游

信息在程序中的表示 系统中的所有信息——包括磁盘文件、存储器中的程序、存储器中存放的用户数据以及网络上传送的数据，都是由一串位表示的。区分不同数据对象的唯一方法是我们读到这些数据对象的上下文。 编译系统 程序在系统上运行，需要先经过编译，转化为一系列的低级语言指令，这些指令并被以可执行文件的格式打包，以二进制磁盘文件的形式存放起来。整个编译系统由四部分组成：预处理器、编译器、汇编器和链接器。 以C语言程序为例解释这四个阶段： 预处理阶段：预处理器将源程序进行修改，根据源文件的命令读取对应系统文件的内容，将其插入到程序文本中，得到另一个被修改的源程序（文本文件）； 编译阶段：经过编译器将修改后 …
算法复习日志【一】：背包、队列和栈
2025-03-27 851 字 4 分钟

算法复习日志【一】：背包、队列和栈

背包、队列和栈都是集合的数据类型，区别仅在于删除或者访问对象的顺序不同。 而对于存储对象集合的方式，有数组和链表两种，常被分别称为顺序存储和链是存储。 下面关于每个数据类型，都将提供数组和链表两种代码实现方式。 链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node 的引用， 该结点含有一个泛型的元素和一个指向另一条链表的引用 特点： 可以处理任意类型的数据 所需的空间总是和集合的大小成正比 操作所需的时间总是和集合的大小无关 背包（Bag） 帮助用例收集元素并迭代遍历所有收集到的元素 特点： 不支持删除元素 迭代顺序不确定且与用例无关 数组实现： 链表实现： …