算法

简介 快速排序算法是对冒泡排序算法的一种改进。平均时间复杂度$O(nlogn)$，最坏时间复杂度$O(n^2)$。 快速排序的基本思想：每趟排序选择一个基准值pivot，使得小于pivot的元素和大于pivot的元素分隔于pivot两侧，即每一趟确定了一个元素的位置。然后对基准值两侧的区间进行递归，以达到整个序列有序。 ...

简介 Johnson算法是求解多源最短路的算法之一，核心操作是re-weight，适用于不包含负环（负权回路）的图。时间复杂度$O(nm+nmlogm)$。 ...

简介 Floyd-Warshall算法是求解多源最短路的算法之一，核心思想是动态规划，适用于不包含负环（负权回路）的图。时间复杂度$O(n^{3})$，空间复杂度$O(n^{2})$。 ...

简介 Bellman-Ford算法是求解单源最短路的算法之一，适用于可包含负边权的有向和无向图，可以判断是否包含负环（注意，如果是包含负权回路则不存在最短路问题）。时间复杂度$O(nm)$。 ...

简介 Dijkstra算法是求解单源最短路的算法之一，核心思想是贪心，只适用于边权为正的无向和有向图。原复杂度$O(n^{2})$，优化后时间复杂度能到$O(mlog_{m})$。 ...

简介 字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串）。优点是利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。 ...

简介 最小表示法，求所有与某个字符串循环同构的字符串中，字典序最小的那个。比如说一个字符串lordash，它长度为7，也就是说最多有七种循环同构的方法。 ...

简介 Manacher’s Algorithm是用来查找一个字符串的最长回文子串的线性方法，由一个叫Manacher的人在1975年发明的。中文谐音“马拉车”算法。时间复杂度O(|S|)。 ...

简介 给定长度为n的文本串S和长度为m的模式串T，定义extend[i]为S[i…n-1]与T[0…m-1]的最长公共前缀长度，求extend[i]。当extend[x]==m时，则可知文本串S中包含模式串T，并且首位置为x，而这正是KMP算法处理的模式匹配问题。相较于KMP算法，扩展KMP算法能找到文本串S中所有模式串T的匹配，更一般地，可以知道文本串S中以每个字符开始的后缀与模式串T的最长公共前缀长度，时间复杂度O(n+m)。 ...

简介 Knuth-Morris-Pratt字符串查找算法，简称为“KMP算法”，常用于在一个文本串S内查找一个模式串T的出现位置。这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。时间复杂度O(|S|+|T|)。 ...

Fibonacci博弈 基本的斐波那契博弈（Fibonacci Game）描述如下： 有一堆数量多于一的物品，两人轮流取走物品，第一次至少取一个，但不能取完，从第二次开始每个人最少取一个，最多取对手上次取的两倍。 ...

Wythoff博弈 基本的威佐夫博弈（Wythoff Game）描述如下： 有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，每次至少取一个，多者不限，最后取光者得胜。 ...

Bash博奕 基本的巴什博弈（Bash Game）描述如下： 有一堆n个物品，两人轮流取走物品，每次至少取一个，最多取m个，最后取光者获胜。 博弈过程如下： 如果n<m，那么先手可以一次取完。先手必胜。 ...

Nim博弈 基本的尼姆博弈（Nim Game）描述如下： 有若干堆各若干个物品，两个人轮流从某一堆取任意多的物品，每次至少取一个，多者不限，最后取光者得胜。 博弈过程如下： ...

公平组合游戏 公平组合游戏（Impartial Combinatorial Games）简称ICG，大致定义如下： 游戏有2名选手 对于游戏任何一种可能的局面（position），合法的操作集合只取决于这个局面本身 选手轮流操作（move），且只能在合法操作集合中选择 在游戏出于某状态，当前选手合法操作集合为空时判负，游戏结束 查看解析 一个公平游戏可以抽象地用一个有向无环图来表示，这个图中每个点都对应一个状态，每条有向边代表从一个状态到另一个状态的合法操作。 ...