空间阶层定理
在计算复杂性理论中，空间阶层定理（）是一组结论，它们表明在一定条件下，确定型和不确定型图灵机在可用的（渐进）存储空间越多时，能用于解答的问题也就越多。例如，一个确定型图灵机在使用n\log{n}存储空间时可以求解比使用n存储空间时更多的决定性问题。在时间复杂度分析中的类似结论是时间阶层定理。 阶层定理的提出建立在这样的直觉之上：能允许使用的时间或空间越多，就应该能求解更多函数（或决定更多语言）。阶层定理可以用来展现时间或空间复杂度类可以…
标签：#算法分析
共 20 篇文章
计算机程序设计艺术
《计算机程序设计艺术》（），簡稱TAOCP，是美國電腦科學家高德纳（）编著的关于计算机程序设计之七卷本著作。作者並因此获得美国计算机协会1974年图灵奖。 概述 1962年，高德纳還是個研究生的時候就開始了程式設計的工作，在攻讀博士期間，艾迪生韋斯利公司（Addison-Wesley）的顧問Richard Varga找他出書，因課業繁忙，一時沒時間草稿。1963年高德納獲得加州理工學院數學博士學位，開始投入撰寫工作。1968年，當時31…
水塘抽樣
水塘抽樣（）是一系列的隨機算法，其目的在於從包含n個項目的集合S中選取k個樣本，其中n為一很大或未知的數量，尤其適用於不能把所有n個項目都存放到内存的情況。最常見例子為在其論文中所提及的算法R。 參照Dictionary of Algorithms and Data Structures所載的O(n)算法，包含以下步驟（假設数组S以0開始標示）： 從S中抽取首k項放入「水塘」中 對於每一個S[j]項（j ≥ k）： 隨機產生一個範圍從0…
时间复杂度
在计算机科学中，算法的时间复杂度（time complexity）是一个函数，用于定性描述算法的运行时间随输入长度增长而变化的情况；这里的输入长度通常指表示输入值的字符串长度。时间复杂度常用大O符号表述，并忽略函数中的低阶项和首项系数。采用这种表述时，时间复杂度也可称为渐近时间复杂度，即考察输入规模趋近无穷时的情况。例如，如果一个算法对于任何大小为 n（且 n 大于某个 n0）的输入，至多需要 的时间运行完毕，则该算法的渐近时间复杂度是…
随机化算法
隨機化演算法（）是在邏輯或執行過程中使用隨機性的演算法。這類演算法通常使用均勻隨機位元作為輔助輸入，以引導演算法的行為，並期望在所有可能的隨機選擇之平均情況下取得良好效能。因此，隨機化演算法的執行時間、輸出結果，或兩者都可能是隨機變數。 隨機化演算法可依其對正確性與執行時間的保證分為不同類型。一類演算法會使用隨機輸入，並總是以正確答案終止，其執行時間可能根據隨機選擇而改變，這類演算法稱為拉斯維加斯演算法。另一類演算法通常具有固定或有界的…
银河式算法
银河式算法（）不是某一种具体算法的名称，而是一类对于极大规模数据表现特别优异的复杂算法。这类算法在常规问题中往往无法展现出优势，甚至效率低于一般的解决方案，而当数据规模足够大时，效率将提升到不可思议的程度。这里的“足够大”实际上已经脱离了现实需求，以至于这类算法从未在实践中发挥作用。“银河式算法”一词首先由理查德·立普顿和肯·里根提出，“银河式”意味着面对数据规模之大如银河中的繁星，且“不会与地球上的问题打交道”。 银河式算法的著名示例…
大O符号
大O符号（），又稱為漸近符號，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，一般是用来刻画被截断的无穷级数尤其是渐近级数的剩余项；在计算机科学中，用来分析算法复杂性的方面非常有用。 大O符号是由德国数论学家保罗·巴赫曼在其1892年的著作《解析数论》（Analytische Zahlentheorie）首先引入的。而这个记号则是在另一位德国数论学家愛德蒙·蘭道的著…
算法分析
在计算机科学中，算法分析（）是分析执行一个给定算法需要消耗的计算资源数量（例如计算时间，存储器使用等）的过程。算法的效率或复杂度在理论上表示为一个函数。其定义域是输入数据的长度（通常考虑任意大的输入，没有上界），值域通常是执行步骤数量（时间复杂度）或者存储器位置数量（空间复杂度）。算法分析是计算复杂度理论的重要组成部分。 理论分析常常利用渐近分析估计一个算法的复杂度，并使用大O符号、大Ω符号和大Θ符号作为标记。举例，二分查找所需的执行步…
分支因子
]] 在电脑运算、树数据结构、賽局理論领域中，分支因子（）是每个下的子结点数，即出度。如果各个结点分支因子不同，则可以计算平均分支因子。 例如，在国际象棋中，如把一步合法走法算作一个“结点”，那么平均分支因子据信约为35。这表示，棋手每一步走棋平均有大约35种合法走法。相比之下，围棋的分支因子为250。 }}
元素唯一性问题
元素唯一性问题（）是計算複雜性理論中判断列表内所有元素是否唯一的问题。关于这一问题的研究已经完备，可以通过许多不同的计算模型解决。其中一种方法就是通过给列表排序，检验是否存在连续相等元素；也可以借由随机化算法将元素插入哈希表中，比较放在哈希表相同位置元素，从而在线性时间复杂度解决这一问题。通过将问题转化为查找问题可以最大程度优化算法的时间复杂度。 决策树的复杂度 已知对于一组数字列表，其时间复杂度是O(n log n)，或言之其时间复杂…
平摊分析
平摊分析，又称摊还分析、-{zh-cn:均摊分析;zh-tw:平攤分析}-（）是計算機科學中的一种算法分析方法，常用於分析資料結構（特别是動態的資料結構）的复杂性。 对于某些数据结构来说，其操作在某些情况下需要耗费相当大的运算资源，但大部分时候开销显著小于最坏情况。如果只使用最坏情况分析，可能会错误地低估其在实际使用时的效率。由于输入的类型、长度等因素都可能影响某一操作的开销，平摊分析通过考虑一组包含了各种不同操作的序列，将少数开销较大…
确定性算法
确定性算法（）是计算机算法的一类。如果以算法的每一步骤是否确定来分类，计算机算法可以分为确定性算法和非确定性算法（）。
算法效率
计算机科学中，算法效率是算法的一种属性，算法效率与算法使用的计算资源量的大小有关。分析算法以确定其资源使用情况，即可根据不同资源的使用情况来衡量算法的效率。算法效率可以被认为类似于某个重复或持续过程的生产力大小。 为获得最大效率，一般希望能够尽量减少资源使用量。然而，时间复杂度和空间复杂度等不同的资源不能直接比较，因此通常两种算法中哪一种更有效率取决于哪种效率计量被认为是最重要的。 例如，冒泡排序和Timsort都是将一个列表中的每一项…
多對數函數
n的多對數函數（polylogarithmic function）也稱為幂对数，是指n的對數的多項式 :a_k \log^k(n) + \cdots + a_1 \log(n) + a_0 其中的是表示。 在計算機科學中，多對數函數在一些演算法時間和空間複雜度的數量級中用到（多對數級，PolyL）。 此外，多對數函數的指數成長是，類似多項式成長，若時間複雜度以準多項式成長的演算法，稱為，類似多項式時間。 所有多對數函數都符合以下的形式 …
大Θ符号
大Θ符号表示函数在某个区间上的渐近关系。如果两个函数在某个区间上的上界和下界都分别为另一个函数，那么这两个函数在该区间上是渐近相等的，可以用大Θ符号表示为： f(n) = Θ(g(n)) 其中，n 是区间的变量。 性质 大Θ符号具有以下性质： 反对称性：如果 f(n) = Θ(g(n))，那么 g(n) = Θ(f(n))。 传递性：如果 f(n) = Θ(g(n))，g(n) = Θ(h(n))，那么 f(n) = Θ(h(n))。 …
半指數函數
在數學上，半指數函數（Half-exponential function）是指數函數的；換句話說，若f是一個半指數函數，則f與自己的複合函數會是一個指數函數： f\bigl(f(x)\bigr) = ab^x, 其中是常數。 解析解的不存在性 假若以加減乘除等標準算數運算、指數、對數及實數常數等來表達一個函數f，那麼f\bigl(f(x)\bigr)要不就是次指數的，要不就是超指數的，因此不可能是半指數函數。 建構 有無限多的函數，其半…
伪多项式时间
在计算理论领域中，若一个数值算法的时间复杂度可以表示为输入数值N的多项式，则称其时间复杂度为伪多项式时间。这是由于，N的值是N的位数的幂，故该算法的时间复杂度实际上应视为输入数值N的位数的幂。 一个具有伪多项式时间复杂度的NP完全问题称之为，而在P!=NP的情况下，若一个NP完全问题被证明没有伪多项式时间复杂度的解，则称之为。 例子 在素性测试}-中，使用较小的整数逐个对被测试数进行试除的算法被认为是一个伪多项式时间算法。对于给定的整数…
空间复杂度
在计算机科学中，一个算法或程序的空间复杂度定性地描述该算法或程序运行所需要的存储空间大小。空间复杂度是相应的输入值的长度的函数，它表示一个算法完全执行所需要的存储空间大小。 和时间复杂度类似，空间复杂度通常也使用大O记号来渐进地表示，例如O(n)、O(n\log n)、O(n^\alpha)、O(2^n)等；其中用来表示输入的长度，该值可以影响算法的空间复杂度。 就像时间复杂度的计算不考虑算法所使用的空间大小一样，空间复杂度也不考虑算法…
大Ω符号
大Ω符号的定义与大O符号的定义类似，但主要区别是，大O符号表示函数在增长到一定程度时总小于一个特定函数的常数倍，大Ω符号则表示总大于。 用数学语言描述即是，f(\nu)=\Omega[g(\nu)]若存在x_1, \kappa使得： 对于所有\forall x>x_1, f(x)>\kappa g(x). 特性 大Ω符号与大O符号正好相反，即： \begin{cases} f(\nu)=\Omicron[g(\nu)]\\ g(\nu)…
計算時間
在計算複雜度理論中，計算時間是種計算抽象機器必須在某些特定計算中花費的步驟數。任何抽象機器花費的計算時間都是一種用以解決計算問題的計算資源。很多重要的複雜度類，都是依照在某些抽象機器上花費特定量級的計算時間而定義的。這些時間複雜度類別共想許多特徵，但它們的相互關係以及複雜度類對其他計算資源的影響仍未充份明瞭。 最常用以度量計算時間的抽象機器就是圖靈機。任何抽象機器，只要擁有 #狀態控制能力與 #可記載狀態控制磁讀寫頭造成的計算時間的磁帶…