主定理
在演算法分析中，主定理（）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。这种方法最初由喬恩·本特利、和在1980年提出，在那里被描述为解决这种递推的“天下無敵法”（Master method）。此方法经由经典演算法教科书、、羅納德·李維斯特和的《算法导论》推广而为人熟知。 不过，并非所有递推关系式都可应用支配理论。该定理的推广形式包括。 支配理论 假设有递归关系式 :T(n) = a \; T\!\left(\fr…
标签：#渐近分析
共 17 篇文章
极限 (数学)
极限（）是函数在自變量無限變大或無限變小或在某個區間時所接近的值，也是數學分析或微積分的重要基础概念，连续和导数都是通过极限来作定义。極限分為描述一个序列的下標愈來越大时的趋势（序列極限），或是描述函数的自变量接趨近某個值時的函数值的趋势（函數極限）。 函数极限可以推广到网中，而数列的极限则与范畴论中的极限和有向极限密切相关。 概念 数列极限 以数列a_n = \frac{1}{n}为例，直觀上随着n的增大，a_n越来越接近0，于是可以…
匹配渐近展开法
匹配渐近展开法（）是数学中用于获得方程或方程组高精度近似解的一种常用方法，尤其常用于奇异摄动微分方程的求解。 对于许多奇异摄动问题而言，可以将定义域分成两个或多个部分。其中一部分（通常是范围最大的部分）可以通过正则摄动理论获得渐近展开级数解。然而这个解在其他较小的部分则十分不精确。如果这些部分处于定义域边界上被称为边界层，处于定义域中间则称为内层。可以将边界层或内层内的求解问题当作一个独立的摄动问题处理，以获得相应的“内解”（之前通过正…
银河式算法
银河式算法（）不是某一种具体算法的名称，而是一类对于极大规模数据表现特别优异的复杂算法。这类算法在常规问题中往往无法展现出优势，甚至效率低于一般的解决方案，而当数据规模足够大时，效率将提升到不可思议的程度。这里的“足够大”实际上已经脱离了现实需求，以至于这类算法从未在实践中发挥作用。“银河式算法”一词首先由理查德·立普顿和肯·里根提出，“银河式”意味着面对数据规模之大如银河中的繁星，且“不会与地球上的问题打交道”。 银河式算法的著名示例…
大O符号
大O符号（），又稱為漸近符號，是用于描述函数渐近行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，一般是用来刻画被截断的无穷级数尤其是渐近级数的剩余项；在计算机科学中，用来分析算法复杂性的方面非常有用。 大O符号是由德国数论学家保罗·巴赫曼在其1892年的著作《解析数论》（Analytische Zahlentheorie）首先引入的。而这个记号则是在另一位德国数论学家愛德蒙·蘭道的著…
欧拉-麦克劳林求和公式
是欧拉-麦克劳林求和公式的提出者之一]] 是欧拉-麦克劳林求和公式的提出者之一]] 欧拉-麦克劳林求和公式在1735年由莱昂哈德·欧拉与科林·麦克劳林分别独立发现，该公式提供了一个联系积分与求和的方法，由此可以导出一些渐进展开式。 公式 设为一至少阶可微的函数，{{Smallmath|f= a,b \in \mathbb{Z} }}，则 \begin{align} \sum_{a 其中 表示的阶乘 {{Smallmath|f= f^{(…
外推
在数学中，外推（，又稱外插）是指从已知数据的孤点集合中构建新的数据的方法。与内插类似，但其所得的结果意义更小，而且更加受不确定性影响。 在市场学中，这种方法被用来预测未来产业走向。 外推算法 线性外推 线性外推在已知数据末端创建一条切线，并将其延伸。仅当用于延展近似线性的函数或延展区域离已有数据不远时，线性外推才是有效的。 如果使用离x_点最近的两个数据点(x_{k-1},y_{k-1})和(x_{k},y_{k})插值，线性外推的公式…
迭代對數
迭代對數（）也稱為重複對數，是一個增加非常慢的數學函數，可以視為近似常數。一般會用log n來表示。一實數的迭代對數是指須對實數連續進行幾次對數運算後，其結果才會小於等於1。最簡單的定義以是以下遞迴函數的結果： : \log^ n := \begin{cases} 0 & \mbox{if } n \le 1; \\ 1 + \log^(\log n) & \mbox{if } n > 1 \end{cases} 在計算機科學中，lg …
发散级数
发散级数（）是指（按柯西意义下）不收敛的级数。如级数1 + 2 + 3 + 4 + \cdots和1 - 1 + 1 - 1 + \cdots ，也就是说该级数的部分和全部序列没有一个有穷极限。 如果一个级数是收敛的，这个级数的项一定会趋于零。因此，任何一个项不趋于零的级数都是发散的。不过，收敛是比这更强的要求：不是每个项趋于零的级数都收敛。像调和级数就是每个项趋于零，但不收斂的级数 :1 + \frac{1}{2} + \frac{1…
史特靈公式
史特靈公式（）是一條用來取n階乘近似值的數學公式。一般來說，當n很大的時候，n階乘的計算量十分大，所以史特靈公式十分好用，而且，即使在n很小的時候，史特靈公式的取值已經十分準確。這個公式以的名字命名，雖然亞伯拉罕·棣美弗早於史特靈提出了一個類似的公式，但結果較不精確。 史特靈公式为： :n! \approx \sqrt{2\pi n}\, \left(\frac{n}{e}\right)^{n}. 这就是说，对于足够大的整数n，这两个数…
黎曼-勒贝格定理
在数学分析中，黎曼-勒贝格定理（或黎曼-勒贝格引理、黎曼-勒贝格积分引理）是一个傅里叶分析方面的结果。这个定理有两种形式，分别是关于周期函数（傅里叶理论中关于傅里叶级数的方面）和关于在一般实数域\mathbb{R}上定义的函数（傅里叶变换的方面）。在任一种形式下，定理都说明了可积函数在傅里叶变换后的结果在无穷远处趋于0。这个结果也可以适用于局部紧致的阿贝尔群。 历史 波恩哈德·黎曼发表这个定理的最初版本是在公元1854年，作为他为哥廷根…
渐进最优
在计算机科学中，渐进最优一词用以评价算法的效率。如果已经证实一个问题需要使用Ω(f(n))的资源来解决，而某个算法用O(f(n))的资源来解决这个问题，则该算法就是渐进最优的。 渐进最优的例子包括数据结构动态数组，能够在常数时间内索引，但性能在多数机器上不如普通数组的索引。另外，在所有基于比较的排序算法中，归并排序和堆排序是渐进最优的。 加速 渐近最优算法的不存在性称为加速比。 布鲁姆加速定理表明存在人为构造的加速问题。 然而，目前许多…
渐近展开
在渐近分析中，一个函数的渐近展开被定义为一个函数级数（通常是柯西发散的），该级数的每一个部分和都给出该函数的一个渐近表达式。 形式定义 下面的定义中用到小 o 表示法。 设 {φ()} 为一个函数序列，{} 为一个数列，() 是一个函数，若 : f(z)-\sum_{n=0}^m a_n\phi_n(z)=o(\phi_m(z)),\quad z\rightarrow z_0,\forall m\in\mathbb Z_0^+ 则称级数…
大Θ符号
大Θ符号表示函数在某个区间上的渐近关系。如果两个函数在某个区间上的上界和下界都分别为另一个函数，那么这两个函数在该区间上是渐近相等的，可以用大Θ符号表示为： 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))。 …
大Ω符号
大Ω符号的定义与大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)…
領頭項
在数学方程式、表达式或模型中的领头项（Leading-order term）是数量级最大的。随着变量的变化，方程中不同项的大小也将发生变化，因此，哪些项是领头项也可能发生变化。 参考文献
特殊函数的渐近展开式
特殊函数的渐近展开式 ;安格尔函数 AngerJ(3,x) \approx {\sqrt(2)cos(x+(1/4)Pi)\sqrt(1/x)/\sqrt(Pi)-(35/8)\sqrt(2)cos(x-(1/4)Pi)(1/x)^(3/2)/\sqrt(\pi)-(945/128)\sqrt(2)cos(x+(1/4)\pi)(1/x)^(5/2)/\sqrt(\pi)+O((1/x)^(7/2))} ;艾瑞函数 AiryAi(z)\…