在计算机科学中，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近分析的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n 的输入，它至多需要 5n + 3n 的时间运行完毕，那么它的渐近时间复杂度是 O。
1
在计算复杂性理论中，多项式时间归约是指假设已有解决一个问题的子程序，利用它在时间复杂度内解决另一个问题的归约方法。多项式时间归约有几种不同类型，取决于具体如何使用子程序。
匈牙利算法是一种在时间复杂度内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。
在计算复杂性理论中，多项式时间归约是指假设已有解决一个问题的子程序，利用它在时间复杂度内解决另一个问题的归约方法。多项式时间归约有几种不同类型，取决于具体如何使用子程序。
博耶-摩尔多数投票算法,中文常作多数投票算法、摩尔投票算法等，是一种用来寻找一组元素中占多数元素的常数空间级时间复杂度算法。这一算法由罗伯特·S·博耶和J·斯特罗瑟·摩尔在1981年发表，也是处理数据流的一种典型算法。
鸽巢排序，也被称作基数分类，是一种时间复杂度为
O
{\displaystyle O}
且在不可避免遍历每一个元素并且排序的情况下效率最好的一种排序算法。但它只有在差值很小的范围内的数值排序的情况下实用。
匈牙利算法是一种在时间复杂度内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。
内省排序是由David Musser在1997年设计的排序算法。这个排序算法首先从快速排序开始，当递归深度超过一定深度后转为堆排序。采用这个方法，内省排序既能在常规数据集上实现快速排序的高性能，又能在最坏情况下仍保持
O
{\displaystyle O}
的时间复杂度。由于这两种算法都属于比较排序算法，所以内省排序也是一个比较排序算法。
在计算理论领域中，若一个数值算法的时间复杂度可以表示为输入数值N的多项式，则称其时间复杂度为伪多项式时间。这是由于，N的值是N的位数的幂，故该算法的时间复杂度实际上应视为输入数值N的位数的幂。
在计算机科学中，Aho–Corasick算法是由阿尔佛雷德·艾侯和Margaret J.Corasick 发明的字符串搜索算法，用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数，如果每个子串互相匹配，算法的时间复杂度会近似于匹配的二次函数。
在计算机科学中，Aho–Corasick算法是由阿尔佛雷德·艾侯和Margaret J.Corasick 发明的字符串搜索算法，用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数，如果每个子串互相匹配，算法的时间复杂度会近似于匹配的二次函数。
Mini wiki
