转帖 说实话，这个话题我也没有这个水平写，转个帖吧 转自知乎 【干货】动态规划十问十答 - 知乎专栏 问1 动态规划是个什么鸟蛋？ 答：动态规划是一种通过“大而化小”的思路解决问题的算法。区别于一些固定形式的算法，如二分法，宽度优先搜索法，动态规划没有实际的步骤来规定第一步做什么第二步做什么。所以更加确切的说，动态规划是一种解决问题的思想。这种思想的本质是，一个规模比较大的问题（假如用...

操作系统复习（一） 概述与进程 #OperatingSystem 概述 操作系统的目标： 方便、有效、扩展能力 操作系统提供的服务：程序开发、程序运行、IO设备访问、文件访问控制、系统访问、错误检测和相应。 操作系统的三个重要接口： 指令系统体系结构（ISA）、应用程序二进制接口（ABI）、应用程序二进制接口（API） OS的发展：串行处理、简单批处理、多道批处理、分时...

本节所有图片均选自 https://algs4.cs.princeton.edu/23quicksort/ 快速排序 今天讲述的是一般语言自带的模板排序算法也是应用最广泛的排序算法— 快速排序。 并不是说他最快，而是一般情况下它的性能能够达到普遍最优。 它仅靠一个辅助栈以及NlgN的时间效率，是其他算法所无法结合的两个优点。 快速排序描述 快速排序是一种分治的排序算法，它将一个数组分...

排序算法 今天开始，将进入一个新的领域，各种各样的排序算法。 排序算法可以用一本TAOCP分册的篇幅来讲述，这里肯定不能全部讲到。 今天主要来写一点简单基础的排序算法。 排序算法的时间复杂度 一般来讲基于比较来排序的算法，最快的时间复杂度为O(nlgn)。 来给出一些常见排序算法的时间复杂度： 本文里将一起讲述插入排序、选择排序、冒泡排序、归并排序和希尔排序5种排序算法。 一些...

二分图匹配概述 首先是什么二分图？ 有一个无向图G = (U ∪ V, E) ，所有的顶点可以划分为U，V两个不相交的顶点集，那么就是一个二分图。 二分图的最大匹配就是找到两个集合可以通过边相连且一一对应的最多对数。 如果能够得到一个所有顶点都可以一一对应，那么这个图称为完美匹配。 二分图匹配的应用 二分图匹配问题可以用来解决任务分配的问题，求得可以被分配的最多任务数目之类的问题。 ...

流网络的基本概念和性质 定义：流网络G = (V, E)是一个有向图，图中每条边有一个非负的容量值c，不会有一条边是另一条边的反向边（即不存在u->v 和 v->u同时存在）。且存在一个源点和一个汇点。 容量限制：对于所有的节点，有0≤f(u,v)≤c(u,v) 现在的流量不大于最大容量。 流量守恒：对于除了源点和汇点的节点，流入的流量等于流出的流量。 类流网...

最短路径问题 首先定义最短路径是什么。最短路径就是在有权图中，从顶点s到顶点t的路径中权重最小的那条路。 同样，由于可能出现一点到另一点相同权重的路径，所以最短路径并不是唯一的。 本章节讨论有向图的最短路径问题，无向图可以转换为有向图进行讨论。 加权有向图的数据结构 struct DirectedEdge{ int from; int to; int weight; /...

什么是最小生成树? 在图G上，如果一个强连通图上的每条边上都有一个权重值，权重值可以是一个负数或零。那么一定可以找到一个无环边子集能够把这个图上的所有的点能够连接起来。 这个五环边子集的权重和如果是所有子集中最小的，那么这个边子集构成的一定是一棵树，所以把它称之为 最小生成树。 同样的，最小生成树不一定是唯一的。 最小生成树的性质 最小生成树的边数目一定是V-1，V是图的顶点数。...

什么是拓扑排序？ 拓扑排序和其他排序算法不同，它主要是给有向无环图中所有结点的一种线性排序。 依据什么排序呢？如果有一条从u指向v的边，那么u在排序结果中一定会在v前面。正因如此，所有拓扑排序只对有向无环图有效，如果图中存在任何形式的环路，那么拓扑排序将不会对其产生作用。 简而言之，拓扑排序就是一种能把图放在一条水平线上铺开的算法。 但是重要一点： 拓扑排序算法的结果可能是不同的。 ...

图的基础概念 图的定义： 无向图： 一个图G = (V,E)由顶点（或结点）的非空集V和边的集合E构成，每条边有一个或两个顶点与它相连，这样的顶点称为端点。边连接它的端点。（顶点集为无限的称为无限图，反之称为有限图） 有向图：一个有向图(V,E)由一个非空顶点集V和一个有向边集E组成。每条有向边与一个顶点有序对相关联。与有序对（u，v）相关联的有向边开始于u，结束于v 图的...