时间戳

首页 > 解决方案 > 渐近函数比较

time-complexity - 渐近函数比较

问题描述

我有 2 个功能：

 f(n) = n*log(n)
 g(n) = n^(1.1) * log(log(log(n)))

我想知道这些功能如何相互比较。据我了解，f(n) 的增长速度总是比 g(n) 快。换句话说：f(n) in ω(g(n))

我假设日志基数为 10，但这并不重要，因为可以使用任何基数。我尝试了许多 n 和 c 的组合，因为以下关系似乎成立：

 f(n) ≥ c g(n) ≥ 0

对我来说似乎很突出的一个组合如下：

 c = 0
 n = 10^10

在这种情况下：

f(10^10) = (10^10) log(10^10) = (10^10)*(10) = 10^11
c*g(n)   = 0 * (10^10)^(1.1) * log(log(log(10^10))
         = 0 * (10^11) * log(log(10))
         = 0 * (10^11) * log(1)
         = 0 * (10^11) * 0 = 0

因此 f(n) 将始终大于 g(n) 并且关系将是 f(n) 是 ω(n)。

我的理解在这里正确吗？

编辑：更正

标签： time-complexitybig-ocomputer-scienceasymptotic-complexity

解决方案

首先，突出到你的组合不起作用，因为它是无效的。一个函数f(x)被称为O(g(x))当且仅当存在一个实数x'和正实数c使得f(x)≤cg(x)对于 all x≥x'。您使用c=0，这不是正数，因此使用它来理解渐近复杂性不会有帮助。

但更重要的是，在您的示例中，情况并非如此f(x)=Ω(g(x))。事实上，它实际上是f(x)=O(g(x))。你可以看到因为log(n)=O(n^0.1)（这里是证明），所以nlog(n)=O(n^1.1)，所以nlog(n)=O(n^1.1 log(log(log(n))))，因此f(x)=O(g(x))。

推荐阅读