Yinode Blog

Wubba lubba dub dub

字典树的实现

字典树也被称之为前缀树,是一种根据字母序列为基础的快速检索数据结构

哈希表的实现

哈希表 散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数

算法导论笔记 多线程算法

多线程算法 相对我来说比较局限,因为 js 是单线程的,所以只做了解,后续如果要用到可以在进行进一步的掌握。 首先来讲,目前的大部分算法都是基于单线程

算法导论笔记 全点最短路径算法

复习 在我们之前的学习之中,已经了解三种不同的最短路径算法,他们在某些条件限制下拥有不同的性能 无权图 或者说权重全部相同 可以使用 广度优先搜索(借

算法导论笔记 动态规划番外篇 堆与优先队列

最近在学习动态规划的时候发现非常需要优先队列的的基础,所以转而先学习一下优先队列算法。这里就找了比较通用的堆来入手了解优先队列。 堆 首先这里的

算法导论笔记 十一 最短路径算法

最短路径 最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。 假设我们拥有一条路径 P P 经过一些

算法导论笔记 十一 贪心算法 最小生成树

图论 最小生成树需要你掌握基本的图论 在书的附录中有介绍,可以先去看看 设 V 为 有向图(v,e)的顶点集 那么遍历这个图的成本为 O(V ^ 2) 如果一个有向图 G

算法导论笔记 一 起步

算法 什么是算法 算法(algorithm),在数学(算学)和计算机科学之中,为任何良定义的具体计算步骤的一个序列,常用于计算、数据处理和自动推

算法导论笔记 二 分治法

名词解释 多项式级 即 n^2 n^3 可以被认为是可控的算法复杂度级别 指数级 x^n 级别 非常恐怖 分治法 分治法是一种极为重要的算法设计思想,他的核心思想就是把大问题

算法导论笔记 八 竞争性分析,自组织表

自组织表 先来理解两个概念 在线算法与离线算法 在线算法(也成为线上算法):是一个处理数据的一种方式,他不要求建立数据结构的时候所有数据源全部就绪

算法导论笔记 四 中位数与顺序统计

选择算法 所谓的选择算法,其基本规则就是从一个无序的数组中,找到第 i 小的值。 最简单的做法其实就是将数组排序,下标+1 就是它的 i。但是,就算依托

算法导论笔记 四 二叉搜索树

二叉树 二叉树本身就是非常常见的一种数据结构了,对于这种数据结构当然有一些基本操作 增删改查最大最小等等,一个二叉树的的基本操作都和二叉树的高度

算法导论笔记 四 全域哈希和完全哈希

HASH 算法的缺陷 首先,我们所了解到的所有简单的复杂的 HASH 函数总会拥有一些薄弱点,即输入一些特殊的 key 会很容易返回相同 KEY 导致多条数据插入到同一个槽中,

算法导论笔记 四 哈希表

直接寻址 相对于哈希表来说,直接寻址是一种更为简单的方法,即使用一组键集合 K 来代表一组相应的值 U,但是直接寻址受限于一个重要的缺陷,即K可能相

算法导论 七 平摊分析,表的扩增,势能方法

动态表 简单阐述一下动态表的基本思想,先建立一个表,当插入的元素大于表的大小时,建立一个新表(大小为旧表的两倍),并将旧表中的所有数据复制到新

算法导论笔记 九 动态规划

动态规划 动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过

算法导论笔记 五 扩充的数据结构、动态有序统计和区间树

这一章的主要内容其实是如何利用现有的数据结构来扩充成一个新的数据结构,并让这种新的数据结构具有一些神奇的特性。 动态顺序统计 我们在前面就学习了

算法导论笔记 六 跳跃表

跳跃表(skiplists) 跳跃表是一种增强版的链表,他能在O(lgn)的时间内完成搜索。 首先,我们熟知的链表本身具有的特性就是容易删除与增