给定代码的复杂性？

我试图找出作为问题大小n的函数的给定代码的复杂性。给定代码的复杂性？

sum = 0; 

if (EVEN(n)) 
    for (i = 0; i < n; i++) 
     if (i%2 == 0) 
     O(logn) 
     else 
     sum ++; 
else 
    sum = sum + n;

这是我的答案，但我不知道我是否做得正确。

sum=0; is equal to O(1)。

第一个if else循环由嵌套for循环组成，并带有嵌套if语句。所以它将是for循环内的代码的n倍。由于它的if语句并且将是块1或块2.由于O(logn)比sum ++慢，因此它是O(1)它是O(logn)。所以它是O(n)*O(logn)。

因此最终答案是O(1) + n*O(logn)。它是否正确？？

来源

2012-10-09 Steve S

我在想最好的情况和平均情况。这是我的解释，这听起来正确吗？现在我们来考虑最好的情况，其中n不是偶数。由于n甚至不是第一个if语句内部的代码不会执行。所以我们需要看代码sum = sum + n。这是O（1）的运行时间。把它加起来就是O（1）+ O（1）= 2 * O（1），它等于O（1）。所以最好的情况是O（1）。平均值为O（n * log（n））+ O（1）/ 2 –

是的，O（nlog（n））是复杂度。

来源

2012-10-09 18:38:05 FSP

我在想最好的情况和平均情况。这是我的解释，这听起来正确吗？现在让我们考虑最好的情况，其中n不是偶数。由于n甚至不是第一个if语句内部的代码不会执行。所以我们需要看代码sum = sum + n。这是O（1）的运行时间。把它加起来就是O（1）+ O（1）= 2 * O（1），它等于O（1）。所以最好的情况是O（1）。平均值为O（n * log（n））+ O（1）/ 2 –

如果你在谈论最差的运行时间，Yeap似乎是正确的。您可以将O(n)*O(logn)重写为O(n*log(n))。

来源

2012-10-09 18:31:04

给定代码的复杂性？

回答

相关问题