我有计算复杂性的问题 [英] I have problem with calculate complexity

问题描述

你好....我有计算二次循环的复杂性的问题

Hello ....I have problem with calculate complexity for second loop

f=1;
x=3;
for (int i = 1; i <= n; i*=2) 
   for (int j = 1; j <= i * i; j++) 
      if (i % j == 0) 
      for (int k = 1; k <= j; k++) 
         f=f*x;

我尝试过：



我计算第三个循环复杂度

结果是O（j）

What I have tried:

I calculate the third loop complexitiy
the result is O(j)

推荐答案

我建​​议你一个实验方法，运行下面的程序，看看输出。它提供了一些见解，可以让你能够理解实际的算法渐近行为。

I suggest you an experimental approach, run the folllowing program and have a look at the output. It gives some insight and could make you able to understand the actual algorithm asymptotic behaviour.

using namespace std;

int main()
{
  const int MAXN = 1000; // try different values

  for (int  n=1; n<MAXN; ++n)
  {
    int count = 0;
    cout << "********************************\nn=" << n << "\n";
    for (int i = 1; i <= n; i*=2)
      for (int j = 1; j <= i * i; j++)
        if (i % j == 0)
          for (int k = 1; k <= j; k++)
          {
            cout << i << " " <<  j  << " " << k  << "\n";
            ++count;
          }
    cout << count <<  endl;
  }
}

这篇关于我有计算复杂性的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！