这个算法的大欧、大欧米茄和大Theta是什么？

Question

我正在阅读算法设计手册，我被塞进了这个问题在这里输入图像描述。

我想，哦，是O(nlogn)，但我不确定，欧米茄和西塔呢？

Answer 1

在描述中，TIME (t)将其作为定义复杂性的关键，而另一个键则是空间(S)。

时间效率的理论分析

• 通过确定基本操作的重复次数与输入大小的函数来分析时间效率。
• Basic操作：对算法C(n)的运行时间贡献最大的操作

​

​

函数的增长与渐近表示法

• 当我们研究算法时，我们感兴趣的是根据它们的效率来描述它们。
• 我们通常感兴趣的是算法运行时间的增长顺序，而不是具体的运行时间。这也被称为渐近运行时间。
• 我们需要开发一种方法来讨论函数的增长率，这样我们就可以比较算法。
• 渐近表示法给出了一种根据增长速度对函数进行分类的方法。

1.大O表示法

• 定义：f (n) = O(g(n))当且仅当存在两个正常数c和n0 F(N)\x{e76f}\x{e76f}(N)\x{e76f}\x{e76f}(N)\x{e76f}(N)，n0 (N)，≤，c，g(N)，x(N)，g(N)，x(N)，g(N)，f(N)，g(N)，x，g，g(N)，f(N)，c，g(N)，f(N)，f(N)，c，g(N)
• 如果f (n)是非负的，我们可以将最后一个条件简化为 所有n个n0的0≤f (n)≤c g(n)
• 我们说 f(n)是g(n)的大O

随着n的增加，f (n)的生长速度不快于g(n)。换句话说，g(n)是f (n)上的渐近上界。

​

​

2.Ω符号

• 定义:F (n) =Ω(g(n))当且仅当有两个正常数c和Ω使得 F(N)\x{e76f}\x{e76f}(N)\x{e76f}\x{e76f}(N)\x{e76f}(N)，n0 (N)，≥，c，g(N)，x(N)，g(N)，x(N)，g(N)，f(N)，g(N)，x，g，g(N)，f(N)，c，g(N)，f(N)，f(N)，c，g(N)
• 如果f (n)是非负的，我们可以将最后一个条件简化为 所有n个n0的0≤c g(n)≤f (n)
• 我们说 f (n)是g(n)的omega

随着n的增加，f(n)的生长速度并不比g(n)慢。换句话说，g(n)是f(n)上的渐近下界。

​

​

3.Θ符号

• 定义:F (n) =Θ(g(n))当且仅当存在三个正常数c1、c2和n0 所有n个n0的c1\g(N)\x{e76f}\x{e76f}f(N)\x{e76f}\x{e76f}(N)\x{e76f}\x{e76f}\
• 如果f(n)是非负的，我们可以将最后一个条件简化为 0 c1 g(n) c2 g(n)≤f (n)≤≥g(N)
• 我们说 f(n)是g(n)的θ

随着n的增加，f(n)的生长速率与g(n)相同。换句话说，g(n)是f(n)上的渐近紧束缚。

​

​

Answer 2

给定算法的时间复杂度为

​

​

根据斯特林近似

​

​

上述函数的上、下界：

​

​

因此，我们得到

​

​