锐客网

  1. 首页 > 睿知 > it技术 > >

算法的渐近分析（函数的增长）

本文概述

  • 为什么渐近符号很重要？
  • 渐近符号
算法的资源通常表示为与输入有关的函数。通常, 此功能比较麻烦且工作复杂。为了有效地研究功能增长, 我们将功能缩减到重要部分。
Let f (n) = an2+bn+c

在此函数中, n2项主导着当n变得足够大时的函数。
在这方面, 称谓词是我们对简化功能感兴趣的东西。我们忽略所有常数和系数, 而是查看与n有关的最高阶项。
渐近符号：
“渐近”一词的意思是任意接近一个值或曲线（即采取某种限制）。
渐近分析
这是一种表示限制行为的技术。该方法在整个科学中都有应用。它可用于分析某些大型数据集的算法性能。
1.在计算机科学中的算法分析中, 考虑将算法应用于非常大的输入数据集时的性能
最简单的示例是函数?（n）= n2 + 3n, 当n非常大时, 项3n与n2相比微不足道。函数“?（n）渐近等效于n2为n→∞”, 此处的符号表示为?（n）?n2。
渐近符号用于为算法编写最快和最慢的运行时间。这些情况也分别称为“最佳情况”和“最坏情况”。
“以渐进表示法, 我们得出了与输入大小有关的复杂度。（以n为例）
【算法的渐近分析（函数的增长）】“这些表示法很重要, 因为在不增加运行算法成本的情况下, 我们可以估算算法的复杂性。”
为什么渐近符号很重要？ 1.它们给出了算法效率的简单特征。
2.它们允许比较各种算法的性能。
渐近符号 渐近符号表示法是一种比较函数的方法, 该函数忽略常数因子和较小的输入大小。使用三种符号来计算算法的运行时间复杂度：
1. Big-oh表示法：Big-oh是表达算法运行时间上限的形式方法。它是最长时间的度量。当且仅当存在正常数c并且使得
f (n) ? k.g (n)f(n)?k.g(n) for n> n0n> n0 in all case

因此, 函数g（n）是函数f（n）的上限, 因为g（n）增长快于f（n）
算法的渐近分析（函数的增长）

文章图片
例如：
1. 3n+2=O(n) as 3n+2≤4n for all n≥2 2. 3n+3=O(n) as 3n+3≤4n for all n≥3

因此, f（n）的复杂度可以表示为O（g（n））
2. Omega()表示法：函数f（n）=Ω（g（n））[读作“ n的f是n的g的欧米茄””, 当且仅当存在正常数c和n0使得
F (n) ≥ k* g (n) for all n, n≥ n0

算法的渐近分析（函数的增长）

文章图片
例如：
f (n) =8n2+2n-3≥8n2-3=7n2+(n2-3)≥7n2 (g(n))Thus, k1=7

因此, f（n）的复杂度可以表示为Ω（g（n））
3. Theta（θ）：函数f（n）=θ（g（n））[读作“ f是n的g的θ”], 当且仅当存在正常数k1, k2和k0使得
k1 * g (n) ≤ f(n)≤ k2 g(n)for all n, n≥ n0

算法的渐近分析（函数的增长）

文章图片
例如：
3n+2= θ (n) as 3n+2≥3n and 3n+2≤ 4n, for nk1=3, k2=4, and n0=2

因此, f（n）的复杂度可以表示为θ（g（n））。
Theta表示法比big-oh和Omega表示法更精确。如果g（n）既是上限又是下限, 则函数f（n）=θ（g（n））。

    推荐阅读


    上一篇：算法设计技术

    下一篇：分析算法控制结构