我得到了这两个算法,每个算法都有两个 for 循环——在我看来,第一个算法的运行时间是二次方的。第二种算法是否具有相同的运行时间 - O(n^2)?
算法 1:
for (int i = 1..n) {
for (int j = 1..n) {
// sort m[i, j]
}
}
算法 2:
for (int i = 1..n) {
for (int j = i..n) {
// sort m[i, j]
}
}
我检查了以前的类似帖子(大 O 表示法)但找不到任何东西来解决我的问题 - 如果你这样做,请指出正确的方向。
谢谢!
最佳答案
下面分析算法2,另一个类似。
让我们首先同意 sort m[i, j]
是 O((j-i)lg(j-i))
。
Alg 2 = O(sum_{i=1}^n sum_{j=i}^n (j-i)lg(j-i))
<= O(sum_{i=1}^n sum_{j=i}^n (n-i)lg(n-i))
<= O(sum_{i=1}^n (n-i)^2 lg(n-i))
= O(sum_{i=1}^n i^2 lg(i))
<= O(sum_{i=1}^n i^2 lg(n))
= O(n^3 lg(n))
另一方面
Alg 2 = O(sum_{i=1}^n sum_{j=i}^n (j-i)lg(j-i)) ; take 1/2 of terms
>= O(sum_{i=n/2}^n sum_{j=(i+n)/2}^n (j-i) lg(j-i))
>= O(sum_{i=n/2}^n sum_{j=(i+n)/2}^n (n-i)/2 lg((n-i)/2))) ; because j>=(i+n)/2
>= O(sum_{i=n/2}^n ((n-i)/2)^2 lg((n-i)/2)))
>= O(sum_{i=n/2}^{(n+n/2)/2} ((n-i)/2)^2 lg((n-i)/2))) ; 1/2 of terms
>= O(sum_{i=n/2}^{3n/4} (n/8)^2 lg(n/8)) ; -i >= -3n/4
= O(n^3 lg(n))
关于time-complexity - 时间复杂度比较,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54578173/