1


我试图找到具有以下等式的选择排序的时间复杂度
T(n)=T(n-1)+O(n)

首先，我认为它的 T(n)=T(n-1)+n .. n 更容易..
想通 了T(n-1) = T(n-2) + (n-1) ， T(n-2) = T(n-3) + (n-2)

这使得T(n) = (T(n-3) + (n-2)) + (n-1) + n它的T(n) = T(n-3) + 3n - 3..

K 而不是 (3) ..T(n) = T(n-k) + kn - k

并且因为 nk >= 0 .. = =>n-k = 0回到n=k

方程它的..T(n) = T(0)// which is C + n*n - n

这使它成为C + n^2 -n..所以它的 O(n^2).. 是我所做的 ryt??

4

2 回答 2

1

是的，您的解决方案是正确的。您正在将 O(n) 与 O(n-1)、O(n-2) ... 结合起来，然后得出 O(n^2)。你可以申请O(n) + O(n-1) = O(n)，但只能是有限的。在一个系列中它是不同的。

T(n) = (0 to n)Σ O(n - i)

忽略 O() 中的 i，你的结果是 O(n^2)

您给出的递归关系T(n)=T(n-1)+O(n)对于选择排序是正确的，它的总体时间复杂度为 O(n^2)。检查此链接以验证

于 2013-03-03T17:30:39.597 回答
0 
In selection sort:

在迭代 i 中，我们找到最小剩余条目的索引 min。然后交换 a[i] 和 a[min]。

因此选择排序使用

(n-1)+(n-2)+....+2+1+0 = (n-1)*(n-2)/2 = O(n*n) compares

and exactly n exchanges(swappings).

从上面

从上面给出的递归关系

=> T(n) = T(n-1)+ O(n)
=> T(n) = T(n-1)+ cn, where c is some positive constant
=> T(n) = cn + T(n-2) + c(n-1)
=> T(n) = cn + c(n-1) +T(n-3)+ c(n-2)

这样继续下去，我们终于得到了

=> T(n) = cn + c(n-1) + c(n-2) + ...... c (total no of n terms)
=> T(n) = c(n*(n-1)/2)
=> T(n) = O(n*n)

编辑

将 theta(n) 替换为 cn 总是更好，其中 c 是某个常数。有助于更轻松地可视化方程式。

于 2013-03-03T17:31:55.330 回答