运行时间的排序代码

Sort(B) 
for i = 0 to (n-1) 
    x = (i+1); 
    for j = (i+2) to n 
     if B[x] > B[j] 
      x = j; 
    if x != (i+1) 
     temp = B[i+1]; 
     B[i+1] = B[x]; 
     B[x] = temp;

什么是运行时间T（n）？问题出在内环（对于j =（i + 2）到n）内环最坏的情况是什么？什么是最好的情况？我认为他们是相同的，因为它是独立的，但我想确定。运行时间的排序代码

来源

2015-06-03 user3552818

无论输入如何，内循环对于给定的外循环迭代总是具有相同的迭代次数。 –

运行时间为O（n^2）。

每个内环需要O(n-i)时间，用于将i的值从0增加到n-1。

这让你有时间的复杂性：

T(n) <= CONST*(n-0 + n-1 + n-2 + ... + n-(n-1)) = 
    = CONST*(1 + 2 + ... + n) = CONST*(n(n+1)/2)

最后的等式来自sum of arithmetic progression。由于n（n + 1）/ 2在O（n^2）中，所以这是时间复杂度。

来源

2015-06-03 19:11:09 amit

它不是这个例子的确切公式，因为内循环做n-i-2。但我们当然可以删除那2，因为它不会改变整个图片。这将是类似于（n *（n + 1）/ 2） - 2 * n –

@GiorgiNakeuri它不应该给出确切的公式，它是与常量的近似值，我添加了CONST *或清晰度。 – amit

谢谢。得到它了：） – user3552818

另一个答案显示算法的运行时间是O（n^2）。我只想指出算法对我来说看起来不完全正确，因为它无法对数组的第一个元素（在这种情况下是B [0]）进行排序。

来源

2015-06-03 19:36:29 Zlol

运行时间的排序代码

回答

相关问题