其中一个是n*sqrt(n)
,另一个是n*log(n)*log(n)
。是否有一种方法来计算哪一个更有效率?
其中一个是n*sqrt(n)
,另一个是n*log(n)*log(n)
。是否有一种方法来计算哪一个更有效率?
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)
大O符号旨在让您快速了解,而不需要进行大量计算。因此,在许多情况下创建图表可能会过度。
大O符号中的常见项包括:
其中,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)
更快。
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)
更有效率。n*sqrt(n)
更有效率。n*log(n)*log(n)
更有效率。log10(n)
、log2(n)
或log(n)
进行分析没有区别。您可以通过执行一个简单的程序来进行经验性尝试,比如下面这个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为底数是因为对数函数和平方根函数之间存在一定的关系。
sqrt(n)
与log(n)*log(n)
进行比较。 - chux - Reinstate Monicasqrt
和log
的时间复杂度吗? - barak manos