我有两个算法A和b
A算法的时间复杂度为O(log n)， B算法的时间复杂度为O(n)。
现在我有一个新的算法C，它的时间复杂度为O(√n)我需要证明(数学上)算法a或算法B是否渐近于算法C
在这方面的任何帮助是非常感激的。谢谢!
√n更接近于O(logn)还是O(n)?
(我假设在下面你实际上是指Θ，而不是O(感谢WhatsUp指出这一点)。否则，这些只是上界，你不能说任何以上界为界的函数的差异
让我们首先从特定的函数log(n)、√n和n开始。显然，log(n) ≤·拉迪奇;n勒;n(您可以使用洛必达法则来查看)。问题是，如果n - √n大于或小于√n - log(n)
在
上的洛必达法则应用lim <子> n→ ∞子>
可以看到这是
lim <子> n→ ∞子> n→ ∞子> n→ ∞子>
·拉迪奇;n 接近 log (n) , n 。
与Θ的计算本质上是相同的，但更繁琐。您需要说明每个函数都有两个常数的边界，并相应地使用上、下两个常数。尽管,明确,如果f , ,和 h θ;(log (n)) , θ;(·拉迪奇;n) ,和θ;(n) ,然后足够大的 n , g (n) - f (n) & lt; & lt;H (n) - g(n).