根据O-表示法，如何判断一个函数比另一个函数更快？
我对如何确定1函数比另一个函数更快还是更慢有一个问题。如果教授使用O(1)和O(n)的例子，我知道O(1)更快，但我只知道通过记忆简单的函数运行时间顺序。但是如果给出更复杂的例子，我不明白如何找到更快的函数。
例如，假设我想比较n^logn和n^(logn)^2和n^(sqrt(n))。如何比较这些函数，并能够判断哪个函数的运行时间最快、最慢(大-O表示法)？是否有一个逐步的进程，我可以跟踪每一次，以便我可以使用比较函数运行时间？
下面是我对上述例子的思考。我知道n^2比n^3快，所以我想比较每个函数的n^____。因此，如果我在每个插件中插入n=1000000，logn将有最小的值，logn^2将有第二个，logn^sqrt(n)将最大。这是否意味着最小值( n^logn )将是最快的，而最大值( n^sqrt(n) )将是最慢的? 1. n^logn(最快) 2. n^logn^2 .n^sqrt(N)(最慢)
回答 2
Stack Overflow用户
发布于 2014-10-02 02:45:01
通常，Big是用N的函数来写的(除了常数，O(1))。
因此，简单地将任何N (3或4个值，或者最好是足够的值来查看曲线)插入到您正在比较和计算的两个函数中就很简单了。如果可以的话就画出来。
但是你不应该这样做，你应该对大O的函数类有一个基本的理解。如果你不能计算它，你仍然应该知道O(log )大于O(1)等等。O符号是最坏的情况。因此，如果您熟悉最常见的函数，通常比较很容易。
这是否意味着最小值( n^logn )将是最快的，而最大值( n^sqrt(n) )将是最慢的? 1. n^logn(最快) 2. n^logn^2 .n^sqrt(N)(最慢)
为了你的比较，是的。O表示法用于比较最坏情况、复杂度或算法类，因此您只需在比较中对所有候选对象假设最坏的情况。您无法从O符号中看出最佳、典型或平均性能将是什么。
Stack Overflow用户
发布于 2014-10-02 02:44:33
比较O符号基本上是比较曲线的问题。我建议你画出曲线-这将有助于你的理解。
如果您使用python，我建议您试试mathplotlib.pyplot。很方便。
https://stackoverflow.com/questions/26153743
复制相似问题
腾讯云开发者
