算法的渐近分析(函数的增长)

本文概述

算法的资源通常表示为与输入有关的函数。通常, 此功能比较麻烦且工作复杂。为了有效地研究功能增长, 我们将功能缩减到重要部分。

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)

算法的DAA渐近分析

例如:

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
算法的DAA渐近分析

例如:

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
算法的DAA渐近分析

例如:

3n+2= θ (n) as 3n+2≥3n and 3n+2≤ 4n, for n
    k1=3, k2=4, and n0=2

因此, f(n)的复杂度可以表示为θ(g(n))。

Theta表示法比big-oh和Omega表示法更精确。如果g(n)既是上限又是下限, 则函数f(n)=θ(g(n))。


微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?