logo标签列表

如何比较两个函数的效率？

ctime-complexitybig-o
3

其中一个是n*sqrt(n)，另一个是n*log(n)*log(n)。是否有一种方法来计算哪一个更有效率？

2
简化：将 sqrt(n) 与 log(n)*log(n) 进行比较。 - chux - Reinstate Monica
你想比较 sqrt 和 log 的时间复杂度吗？ - barak manos
5个回答
6
假设 n*sqrt(n) 和 n*log(n)*log(n) 是你的两个函数的复杂度（大 O），你需要比较这两个表达式。为了快速简便地比较两个简单表达式（也称函数），你可以使用谷歌搜索。只需输入
y = x*log(x)*log(x), y = x*sqrt(x)

在搜索栏中输入，它将绘制两个图形，您可以进行比较。
或者您可以执行函数相减，如：
y = x*log(x)*log(x) - x*sqrt(x)

然后你会得到一张图表，便于检查结果是否大于/小于零。
2

从0,1,...开始为各个值绘制图形，观察哪个函数增长更高。 增长较少的函数更有效率。

我附上两个函数的图像：

enter image description here

左侧是n*log(n)*log(n)，右侧是n*sqrt(n)。你可以看到，n*log(n)*log(n)的增长较少更高效 :)

1
你应该提到用于创建图表的在线网站。 :) - abhishek_naik
需要提到那个名字吗？无论如何，我使用了 fooplot。 - jbsu32
0

大O符号旨在让您快速了解，而不需要进行大量计算。因此，在许多情况下创建图表可能会过度。

大O符号中的常见项包括：

  • O(1)
  • O(log n)
  • O(n)
  • O(n²)
  • O(nc)

其中，O(1)最快，每个都比前一个慢。当然还有更多，但这5个是您经常看到的。

在您的示例中，人们只需要知道：

  • O(n²) = O(n) * O(n)
  • O(log n)比O(n)更快

因此得出：

O(log n) * O(log n)比O(n) * O(n)更快

(因为快速*快速比慢速*慢速更快)

因此得出：

x * O(log n) * O(log n)比x * O(n) * O(n)更快。

0
其中一个是 n*sqrt(n)，另一个是 n*log(n)*log(n)。哪一个更有效率？

简化：

n*sqrt(n) versus  n*log(n)*log(n)
compares the same as 
sqrt(n) versus  log(n)*log(n)
compares the same as 
n versus  power(log(n),4)

注意增长和两者的比率 f(n)/g(n)。
  n        power(log(n),4)  ratio
      1          0             - 
     10          1             10
    100         16             12.3...
   1000         81             39.0...
  10000        256            160.0
 100000        625            771.6...
1000000       1296           4164.9...

如果比率趋近于无穷大，n*log(n)*log(n)更有效率。
如果比率趋近于0，n*sqrt(n)更有效率。
如果比率趋近于正常数，效率相当。
结论：n*log(n)*log(n)更有效率。
注意：使用log10(n)、log2(n)或log(n)进行分析没有区别。
0

您可以通过执行一个简单的程序来进行经验性尝试，比如下面这个Java程序：

public class AlgoTest {
    public static void main(String[] args) {

        final int n = 1024;

        int sum1 = 0;
        int sum2 = 0;

        int b = 2;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < Math.sqrt(n); j++) {
                sum1 ++;
            }
        }
        System.out.println("n*sqrt(n) = " + sum1);

        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= n; j*=b) {
                for (int k = 1; k <= n; k*=b) {
                    sum2 ++;
                }   
            }
        }
        System.out.println("n*log(n)*log(n) = " + sum2);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < sub; j ++) {
                for (int k = 0; k < sub; k ++) {
                    sum3 ++;
                }
            }
        }
        System.out.println("[Sophisticated] n*log(n)*log(n) = " + sum3);
    }
}

其中sum1是一个程序执行迭代次数的变量，其复杂度为n*sqrt(n)，而下一个程序的复杂度为n*log(n)*log(n)。

我选择以2为底数是因为对数函数和平方根函数之间存在一定的关系。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接