时间计算复杂度？

-3

我有这个排序代码，下面是冒泡排序，但我认为这个代码不完全是O（N^2）。我想知道下面这段代码在大O方面的时间计算复杂度是多少。我猜这是O（N.logN）。时间计算复杂度？

代码只是作为例子给出，并没有声称它是可编译的。

for(i = 0; i < n-1; i++) 
{ 
    for(j = 0; j < n-i-1; j++) 
    { 
     if (a[j+1] < a[j]) 
     { 
      temp = a[j]; 
      a[j] = a[j+1]; 
      a[j+1] = temp; 
     } 
    } 
}

来源

2012-02-02 goldenmean

什么“代码在下面”？ – 2012-02-02 10:02:19

@PaulR Blooper纠正 - 现在发布代码。 – goldenmean 2012-02-04 14:51:33

我想这是O（N.logN）。

为什么猜测？看看实际发生了什么...

第一次虽然外环，i == 0.这意味着j将范围从0到n-1。

第二次通过，i == 1，所以j的范围从0到n-2。

尽管第三次，i == 2，所以j的范围从0到n-3。

...

最后一次通过，我== n-1个，所以Ĵ范围从0到0

所以，操作的总数目为n-1 + n-2个+ n-3 + ... + 0.

什么是总和Σi，i = 0..n-1？现在将其转换为大O界限。

来源

2012-02-04 15:25:11 Caleb

Caleb的权利。它可能“感觉”小于O（n^2），因为内循环随着外循环的每次迭代而变短，并且确实比内循环每次变为“n”时更快。然而，它并没有改变整体事实，即工作量与n成指数增长。 – 2012-02-04 16:57:03

@Caleb感谢数学。是的，总的迭代次数似乎是N（N-1）/ 2，所以我看它仍然是O（N^2）。 N.logN（迭代，非递归）算法是什么样的。当我们进行二分搜索时（在一个有序数组上），为什么当我们实际去N - > N/2 - > N/4等时，它被称为logN。将数组分成一半进行搜索？人们总是说二进制搜索==> logN，但我还没有碰到它背后的数学？ – goldenmean 2012-02-04 18:11:23

@goldenmean在二进制搜索中，您将每次搜索的东西数除以2。这意味着需要log2（n）步骤才能找到任何元素。尝试一下：如果n = 8，则需要3个步骤。如果n = 32,5个步骤。 – Caleb 2012-02-04 19:06:00

时间计算复杂度？

回答

相关问题