if语句如何影响时间复杂度？ [英] How does this if statement affect the time complexity?

问题描述

我知道前两个循环是O（n ^ 3），但是我不确定if语句如何影响时间复杂度。

I know that the first two loops are O(n^3), but I am not sure how the if statement affects the time complexity.

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

推荐答案

if 语句对这段代码的整体复杂性有巨大影响。

The if statement has a huge impact in the overall complexity of this code.

是否为O（n ^ 5）但不为O（n ^ 4）。

由于 j 的范围是 1到i * i ，而if仅在 j％i时有效= 0 。

Since j has a range from 1 to i*i and the if will work only when j % i = 0.

这意味着对于每个 i，j 都将运行 i ^ 2 ，当 j％i = 0 时有 i 个案例。

That means for each i, j will work i^2 and there are i cases when j % i = 0.

因此，总体复杂度将为 O（n ^ 4）。

So, the overall complexity will be O(n^4).

要了解它的运行方式，我只需编译代码：

To get an idea how it goes, I just compile the code:

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

这里是输出。

如果有

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

如果没有，则

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）。

这篇关于if语句如何影响时间复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！