1

这个问题是为了修改过去的试卷，只是想知道我是否做得对。

我对此很陌生，所以我对更复杂的问题有点困难。这是其中之一……

如果有人能详细说明这一点，我将非常感激......所以我必须找出这段代码的复杂性......

cout = 0;
for(int i=1 ; i<=n ; i*=3)
   for(int j=1 ; j<=i; j++)
      for(int k=1 ; k<=n ; k++)
          count++;

所以，我试着这样做......我得到了 O(n^2logn).. 它不正确......答案应该是 O(n^2).. 有人可以帮我吗？

4

2 回答 2

1

第二个循环的迭代次数是 $$ 1 + 3 + 9 + ... + m $$，其中 $m$ 大约是 $n$。这总和为 $\Theta(n)$。那么最里面的循环是 Theta(n) 的另一个因素。所以$\Theta(n^2)$。

于 2013-11-06T18:33:45.113 回答
1

确定算法时间复杂度的正式方式：

在此处输入图像描述

于 2014-03-14T23:55:10.863 回答