algorithm - 算法分析：选择最佳算法

Question

我正在尝试解决一个关于比较两种算法在最坏情况下运行时间方面的问题，并找到一种算法比另一种算法运行时间更快的输入大小。

这两种算法是：
A ₁ = 2n log ₁₀ n
A ₂ = 0.1n ²

基本上，我试图解决以下 n 的不等式：
2n log ₁₀ n < 0.1n ²

谁能指出我正确的方向？
我设法达到：
log ₁₀ n < 0.05n ==> n < 10 ^0.05n

但我不知道从这里该怎么做（或者我可能以错误的方式试图解决它）。

提前谢谢你的帮助！

Answer 1

实际上，您正在尝试解决不平等问题

因为算法只会在很短的时间内变得更快，然后对于任何更大的 n 值，算法都会更快。

忽略 n <= 0 的情况，乘以 10，再除以 n 得到：

然后除以 20 并以 10 为底对两边取幂：

使用数值求解器在区间 [1, 40] 上找到 的零点，因为显然 40 是一个上限（因为）。

例如，在 Matlab 中：

>> fzero(@(x) 10^(x/20)- x, 20)

ans =

   29.3531

因此，对于任何 n 到 29 的整数，算法都更快，对于 n > 29，算法获胜。

Answer 2

只需使用 sagemath 绘制函数的图像： plot(0.1 * n * n - 2 * n * log(n, 10), n, 0, 50)