确定最坏情况算法的时间复杂性

这两种算法是否具有Θ（n^2）的相同θ表征？确定最坏情况算法的时间复杂性

int sum = 0; 
for (int i = 0; i < n; i++) 
    for (int j = 0; j < n * n; j++) 
     sum++; 

int sum = 0; 
for (int i = 0; i < n; i++) 
    for (int j = 0; j < i; j++) 
     sum++;

如果不是那么这是否意味着这种表征不是Θ（n^3）？

int sum = 0; 
for (int i = 0; i < n; i++) 
    for (int j = 0; j < i * i; j++) 
     for (int k = 0; k < j; k++) 
      sum++;

来源

2010-09-29 Dan

您怎么看？ – aaronasterling 2010-09-29 02:30:20

我不认为是第一个，但是对于j <我是n^2，但我不知道为什么 – Dan 2010-09-29 02:35:09

你会如何计算两者中的任何一个所采取的步骤？第二个是 – aaronasterling 2010-09-29 02:37:36

@丹，这是第一个你真正的意思j < n * n而非j < n？如果是这样，第一个的时间复杂度是Θ（n^3），不是吗？如果你的意思是j < n，那么我相信前两个都是Θ（n^2）：第一个需要n^2个步骤，第二个需要1 + 2 + ... + n = n（ n + 1）/ 2，即Θ（n^2）。

我在想第三个是Θ（n^4），但它很难证明。当然是O（n^4）。

来源

2010-09-29 02:56:47 LarsH

是的，我的意思是j Dan 2010-09-29 03:21:43

@Dan乘法运算n增加了n，而不是1. for（int i = 0; i 2010-09-29 03:33:25

@Tan当@Dan表示学位时我相信他在谈论指数。所以是的@Dan如果你乘n^k * n，你会得到n ^（k + 1）。我不确定这是不是你问的问题。 – LarsH 2010-09-29 05:07:48

确定最坏情况算法的时间复杂性

回答

相关问题