Как это, если утверждение влияет на сложность времени? - PullRequest
Новая
       0

Как это, если утверждение влияет на сложность времени?

2 голосов
/ 23 января 2020

Я знаю, что первые два цикла - это O (n ^ 3), но я не уверен, как оператор if влияет на сложность времени. 

int sum = 0;
for(int i = 1; i < n; i++) {
    for(int j = 1; j < i * i; j++) {
        if(j % i == 0) {
            for(int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
}

1 Ответ

2 голосов
/ 23 января 2020

Оператор if оказывает огромное влияние на общую сложность этого кода.

Без, если это будет O (n ^ 5), но с, если это O (n ^ 4) ) .

Так как j имеет диапазон от 1 to i*i, и if будет работать только тогда, когда j % i = 0.

Это означает, что для каждого i, j будет работать i^2 и есть i случаев, когда j % i = 0.

Итак, общая сложность будет O(n^4).

Чтобы понять, как это происходит, я просто скомпилировал код: 

   static int count;

   static void rr(int n)
   {
      for (int i = 1; i < n; i++)
      {
         for (int j = 1; j < i * i; j++)
         {
            if (j % i == 0)
            {
               for (int k = 0; k < j; k++)
               {
                  count++;
               }
            }
         }
      }
   }

   public static void main(String[] args)
   {
      for (int n = 50; n < 110; n += 10)
      {
         count = 0;
         rr(n);
         System.out.println("For n = " + n + ", Count: " + count);
      }
   }

Вот вывод.

С if 

For n = 50, Count: 730100
For n = 60, Count: 1531345
For n = 70, Count: 2860165
For n = 80, Count: 4909060
For n = 90, Count: 7900530
For n = 100, Count: 12087075

Без if 

For n = 50, Count: 29688120
For n = 60, Count: 74520894
For n = 70, Count: 162068718
For n = 80, Count: 317441592
For n = 90, Count: 574089516
For n = 100, Count: 975002490

Итак, если сложность O (n ^ 4).

...