渐近符号和 Apriori 分析

在算法设计中，算法的复杂度分析是一个重要的方面。算法复杂性主要与它的性能、运行速度有多快或多慢有关。

算法的复杂度以处理数据所需的内存量和处理时间来描述算法的效率。

算法的复杂度从时间和空间两个角度来分析。

时间复杂度

它是一个函数，根据输入的大小描述运行算法所需的时间。“时间”可以指执行的内存访问次数、整数之间的比较次数、执行某些内部循环的次数，或与算法将花费的实时量相关的一些其他自然单位。

空间复杂度

它是一个函数，根据算法输入的大小来描述算法占用的内存量。我们经常谈到需要“额外”内存，而不是计算存储输入本身所需的内存。同样，我们使用自然（但固定长度）单位来衡量这一点。

空间复杂性有时会被忽略，因为所使用的空间很小和/或明显，但有时它变得与时间一样重要。

渐近分析

算法的渐近分析是指定义其运行时性能的数学基础/框架。使用渐近分析，我们可以很好地得出算法的最佳情况、平均情况和最坏情况。

渐近分析是输入限制的，即，如果算法没有输入，则得出结论在恒定时间内工作。除了“输入”之外，所有其他因素都被认为是恒定的。

渐近分析是指以数学计算单位计算任何操作的运行时间。例如，一个操作的运行时间计算为 f(n)，而另一操作的运行时间可能计算为g (n 2 )。这意味着第一个操作的运行时间将随着n的增加而线性增加，而第二个操作的运行时间将随着n的增加而呈指数增加。类似地，如果n非常小，则两个操作的运行时间将几乎相同。

通常，算法所需的时间分为三种类型 -

  • 最佳情况- 程序执行所需的最短时间。

  • 平均情况- 程序执行所需的平均时间。

  • 最坏情况- 程序执行所需的最长时间。

渐近符号

算法的执行时间取决于指令集、处理器速度、磁盘 I/O 速度等。因此，我们渐近地估计算法的效率。

算法的时间函数由T(n)表示，其中n是输入大小。

不同类型的渐近符号用于表示算法的复杂性。以下渐近符号用于计算算法的运行时间复杂度。

  • O – 大哦

  • Ω - 大欧米茄

  • θ - 大θ

  • o - 小哦

  • ω - 小欧米茄

O：渐近上限

“O”（Big Oh）是最常用的符号。函数f(n)可以表示为g(n)的阶数，即O(g(n))，如果存在正整数 n 的值n 0和正常数c使得 -

$f(n)\leqslant cg(n)$ 在所有情况下 $n > n_{0}$

因此，函数g(n)是函数f(n)的上限，因为g(n) 的增长速度比f(n)快。

大哦符号

例子

让我们考虑一个给定的函数，$f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

考虑$g(n) = n^3$，

$f(n)\leqslant 5.g(n)$ 对于 $n > 2$ 的所有值

因此， f(n)的复杂度可以表示为$O(g(n))$，即$O(n^3)$

Ω：渐近下界

当对于所有足够大的n值存在 $f(n)\geqslant cg(n)$ 的常数c时，我们说 $f(n) = \Omega (g(n))$ 。这里n是一个正整数。这意味着函数g是函数f的下界；在 n达到某个值后， f永远不会低于g。

欧米茄表示法

例子

让我们考虑一个给定的函数，$f(n) = 4.n^3 + 10.n^2 + 5.n + 1$。

考虑 $g(n) = n^3$，对于 $n > 0$ 的所有值，$f(n)\geqslant 4.g(n)$。

因此， f(n)的复杂度可以表示为$\Omega (g(n))$，即$\Omega (n^3)$

θ：渐近紧界

当存在常数c 1和c 2 $c_{1}.g(n) \leqslant f(n) \leqslant c_{2} 时，我们说 $f(n) = \theta(g(n))$ .g(n)$ 对于所有足够大的n值。这里n是一个正整数。

这意味着函数g是函数f的紧界。

θ符号

例子

让我们考虑一个给定的函数，$f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

考虑 $g(n) = n^3$，对于n的所有大值， $4.g(n) \leqslant f(n) \leqslant 5.g(n)$ 。

因此， f(n)的复杂度可以表示为$\theta (g(n))$，即$\theta (n^3)$。

O - 表示法

O 表示法提供的渐近上限可能是渐近紧的，也可能不是渐近紧的。界限 $2.n^2 = O(n^2)$ 是渐近紧的，但界限 $2.n = O(n^2)$ 不是。

我们使用o 符号来表示非渐近紧的上限。

我们正式将o(g(n))（n 的 g 的小 oh）定义为对于任何正常数 $c > 0$ 的集合f(n) = o(g(n))，并且存在一个值 $n_ {0} > 0$，使得 $0 \leqslant f(n) \leqslant cg(n)$。

直观上，在o 表示法中，当n接近无穷大时，函数f(n)相对于g(n)变得微不足道；那是，

$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = 0$$

例子

让我们考虑相同的函数，$f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

考虑 $g(n) = n^{4}$，

$$\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^4}\right) = 0$$

因此， f(n)的复杂度可以表示为$o(g(n))$，即$o(n^4)$。

ω – 符号

我们使用ω 表示法来表示非渐近紧的下界。然而，正式地，我们将ω(g(n))（n 的 g 的小欧米伽）定义为对于任何正常数C > 0的集合f(n) = ω(g(n))，并且存在一个值 $ n_{0} > 0$，使得 $0 \leqslant cg(n) < f(n)$。

例如，$\frac{n^2}{2} = \omega (n)$，但 $\frac{n^2}{2} \neq \omega (n^2)$。关系 $f(n) = omega (g(n))$ 意味着存在以下极限

$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = \infty$$

也就是说，当n接近无穷大时， f(n)相对于g(n)变得任意大。

例子

让我们考虑相同的函数，$f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

考虑$g(n) = n^2$，

$$\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^2}\right) = \infty$$

因此， f(n)的复杂度可以表示为$o(g(n))$，即$\omega(n^2)$。

Apriori 和 Apostiari 分析

Apriori 分析是指在特定系统上运行之前执行分析。该分析是使用某种理论模型定义函数的阶段。因此，我们通过仅查看算法来确定算法的时间和空间复杂度，而不是在具有不同内存、处理器和编译器的特定系统上运行它。

Apostiari 算法分析意味着我们只有在系统上运行算法后才对其进行分析。它直接取决于系统，并且随着系统的不同而变化。

在行业中，我们无法进行 Apostiari 分析，因为该软件通常是为匿名用户制作的，该用户在与行业中存在的系统不同的系统上运行该软件。

在 Apriori 中，这就是我们使用渐近符号来确定时间和空间复杂度随计算机的变化而变化的原因；然而，它们渐近是相同的。