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

本文概述

• 为什么渐近符号很重要？
• 渐近符号

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

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 n
    k1=3, k2=4, and n0=2

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

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