Member 13849940 Ответов: 1

У меня есть проблема с вычислением сложности

Привет....У меня есть проблема с вычислением сложности для второго цикла
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)

OriginalGriff

И что же?
В чем проблема?
А что вы пробовали?
Где ты застрял?
Какая помощь вам нужна?

Member 13849940

Я придерживался этого условия
for (int j = 1; j <= i * i; j++)
если (i % j == 0)

1 Ответов

Рейтинг:
0

CPallini

Я предлагаю вам экспериментальный подход, запустите следующую программу и посмотрите на результат. Это дает некоторое представление и может помочь вам понять фактическое асимптотическое поведение алгоритма.

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;
  }
}