我得到了这两个算法,每个算法有两个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]
}
}
我检查了以前的类似帖子(Big 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))