关于算法复杂度，我怎么知道 n^(0.1) = w[ (log n)^10 ]
How do I know that n^(0.1) = w[ (log n)^10 ] with regard to algorithm complexity
假设 w = 小 omega
一个算法完成一个任务需要n^(0.1)步
另一个算法需要 (log n)^10 来完成任务
问的问题是 n^(0.1) = w((log n)^10) 是否成立。我答错了，说错了。但是，如果从图形上看，即使在数万亿的 n 值下，(log n)^10 似乎支配 n^(0.1)，我也不确定为什么我会弄错。
我试过的:
我试过取f(x)/g(x)的极限看它是否趋于无穷大。然而，经过一轮 L'Hopital 的规则后，这种方法似乎是一个非常复杂的过程。
我也尝试过简单地以图形方式评估 n^(0.1) 是否比 (log n)^10 增长得更快。也许这就是我困惑的根源。我的教授说，在对数与多项式的情况下，任何多项式总是支配对数。但是，我已经尝试将这些函数相互绘制成图形，甚至在 n = 9999999 时，(log n)^10 似乎明显支配 n^(0.1).
我是不是漏掉了什么？ n^0.1 会在某个时刻支配 (log n)^10 吗？
注意：我应该澄清一下，这完全与大 O 符号和算法复杂性有关。其中 n^(0.1) 和 (log n)^10 表示给定算法执行任务所需的步骤。我在问题中添加了一些描述，希望能让事情变得更清楚。
由于您没有指定日志的基数，所以让我们将其设为常量 B。
现在最简单的方法就是证明你想要什么让n = B10m
则n0.1 / (logB n)10 = Bm / (10m)10
现在我们将一个简单的指数与一个简单的多项式进行比较，如果有必要，我们可以证明指数将占主导地位...尽管 n 在它之前会变得相当大确实。
例如，如果我们找到 m 这样 2m = (10m)10 ，我们得到 m = 100 左右，所以 n = 21000.
假设 w = 小 omega
一个算法完成一个任务需要n^(0.1)步
另一个算法需要 (log n)^10 来完成任务
问的问题是 n^(0.1) = w((log n)^10) 是否成立。我答错了，说错了。但是，如果从图形上看，即使在数万亿的 n 值下，(log n)^10 似乎支配 n^(0.1)，我也不确定为什么我会弄错。
我试过的:
我试过取f(x)/g(x)的极限看它是否趋于无穷大。然而，经过一轮 L'Hopital 的规则后，这种方法似乎是一个非常复杂的过程。
我也尝试过简单地以图形方式评估 n^(0.1) 是否比 (log n)^10 增长得更快。也许这就是我困惑的根源。我的教授说，在对数与多项式的情况下，任何多项式总是支配对数。但是，我已经尝试将这些函数相互绘制成图形，甚至在 n = 9999999 时，(log n)^10 似乎明显支配 n^(0.1).
我是不是漏掉了什么？ n^0.1 会在某个时刻支配 (log n)^10 吗？
注意：我应该澄清一下，这完全与大 O 符号和算法复杂性有关。其中 n^(0.1) 和 (log n)^10 表示给定算法执行任务所需的步骤。我在问题中添加了一些描述，希望能让事情变得更清楚。
由于您没有指定日志的基数，所以让我们将其设为常量 B。
现在最简单的方法就是证明你想要什么让n = B10m
则n0.1 / (logB n)10 = Bm / (10m)10
现在我们将一个简单的指数与一个简单的多项式进行比较，如果有必要，我们可以证明指数将占主导地位...尽管 n 在它之前会变得相当大确实。
例如，如果我们找到 m 这样 2m = (10m)10 ，我们得到 m = 100 左右，所以 n = 21000.