在计算机科学中,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近分析的,亦即考察输入值大小趋近无穷时的情况。例如,如果一个算法对于任何大小为 n 的输入,它至多需要 5n + 3n 的时间运行完毕,那么它的渐近时间复杂度是 O。
完全公平排程器,Linux内核的一部分,负责行程排程。参考了康恩·科里瓦斯提出的排程器源代码后,由匈牙利程式员英格·蒙内所提出。在Linux kernel 2.6.23之后采用,取代先前的O(1)排程器,成为系统预设的排程器。它负责将CPU资源,分配给正在执行中的行程,目标在于最大化程式互动效能与整体CPU的使用率。使用红黑树来实作,算法效率为大O符号。
Kademlia是一种通过分散式杂凑表实现的协议算法,它是由Petar Maymounkov与David Mazières为非集中式对等网络计算机网络而设计的。Kademlia规定了网络的结构,也规定了通过节点查询进行信息交换的方式。参与通讯的所有节点形成一张虚拟网。这些节点通过一组数字来进行身份标识。节点ID不仅可以用来做身份标识,还可以用来进行值定位。其实,节点ID与文件散列直接对应,它所表示的那个节点存储着哪儿能够获取文件和资源的相关信息。当我们在网络中搜索某些值的时候,Kademlia算法需要知道与这些值相关的键,然后分步在网络中开始搜索。每一步都会找到一些节点,这些节点的ID与键更为接近,如果有节点直接返回搜索的值或者再也无法找到与键更为接近的节点ID的时候搜索便会停止。这种搜索值的方法是非常高效的:与其他的分散式杂凑表的实现类似,在一个包含n个节点的系统的值的搜索中,Kademlia仅访问大O符号个节点。非集中式网络结构还有更大的优势,那就是它能够显著增强抵御拒绝服务的能力。即使网络中的一整批节点遭受泛洪攻击,也不会对网络的可用性造成很大的影响,通过绕过这些漏洞来重新编织一张网络,网络的可用性就可以得到恢复。
O排程器,Linux内核中的排程器,其使用的排程算法,保证每个行程都能在常数时间内被执行到。因算法效率为大O符号,因此得名。在它之前的排程器,都被称为O排程器。由英格·蒙内提出,在Linux-2.6.0时加入,在版本2.6.23后,被完全公平排程器取代。
颂哈吉-施特拉森算法是渐近快速的大整数乘法算法。是由阿诺德·颂哈吉和沃尔克·施特拉森在1971年发明。若针对二个n位元的整数,其运行的位元复杂度,若以大O符号表示,是
O
{\displaystyle O}
。算法使用在有2+1个元素的环上的迭代快速傅里叶变换,这是一种特别的数论转换。
侏儒排序或愚人排序是一种排序算法,最初在2000年由伊朗计算机工程师Hamid Sarbazi-Azad提出,他称之为“愚人排序”。此后Dick Grune也描述了这一算法,称其为“侏儒排序”。此算法类似于插入排序,但是移动元素到它该去的位置是通过一系列类似冒泡排序的移动实现的。从概念上讲侏儒排序非常简单,甚至不需要嵌套循环。它的平均运行时间是大O符号,如果列表已经排序好则只需O的运行时间。
大Ω符号的定义与大O符号的定义类似,但主要区别是,大O符号表示函数在增长到一定程度时总小于一个特定函数的常数倍,大Ω符号则表示总大于。
大Θ符号是大O符号和大Ω符号的结合。即:
f
=
Θ
[
g
]
{\displaystyle f=\Theta [g]\!}
若
{
f
=
O
[
g
]
f
=
Ω
[
g
]
{\displaystyle {\begin{cases}f=\mathrm {O} [g]\\f=\Omega [g]\end{cases}}}
。
大Ω符号的定义与大O符号的定义类似,但主要区别是,大O符号表示函数在增长到一定程度时总小于一个特定函数的常数倍,大Ω符号则表示总大于。
完全公平排程器,Linux内核的一部分,负责行程排程。参考了康恩·科里瓦斯提出的排程器源代码后,由匈牙利程式员英格·蒙内所提出。在Linux kernel 2.6.23之后采用,取代先前的O(1)排程器,成为系统预设的排程器。它负责将CPU资源,分配给正在执行中的行程,目标在于最大化程式互动效能与整体CPU的使用率。使用红黑树来实作,算法效率为大O符号。