带if语句的嵌套for循环的时间复杂度 [英] Time Complexity of Nested for Loops with if Statements

问题描述

此代码的if语句如何影响此代码的时间复杂度?

How does the if-statement of this code affect the time complexity of this code?

基于以下问题:运行时分析，if语句中的for循环将运行n * n时代.但是在这段代码中， j 超过了 i ，因此，第二个循环运行后， j = i ^ 2 .那么，这使第三个for循环的时间复杂度又如何呢?我知道第一个for循环运行n次，第二个运行 n ^ 2 次，而第三个在触发时运行 n ^ 2 次.因此，复杂度将由 n * n ^ 2(xn ^ 2)给出，其中 n 是if语句为true的次数.复杂度不是简单的 O(n ^ 6)，因为if语句不是n次正确的对吗?

Based off of this question: Runtime analysis, the for loop in the if statement would run n*n times. But in this code, j outpaces i so that once the second loop is run j = i^2. What does this make the time complexity of the third for loop then? I understand that the first for loop runs n times, the second runs n^2 times, and the third runs n^2 times for a certain amount of times when triggered. So the complexity would be given by n*n^2(xn^2) for which n is the number of times the if statement is true. The complexity is not simply O(n^6) because the if-statement is not true n times right?

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

推荐答案

当 j 是 i if 条件为true>;发生 i 次是 j 从0到 i * i 的时间，因此第三个 for 循环仅运行 i 次.总体复杂度为O(n ^ 4).

The if condition will be true when j is a multiple of i; this happens i times as j goes from 0 to i * i, so the third for loop runs only i times. The overall complexity is O(n^4).

for (int i = 1; i < n; i++)
{
  for (int j = 0; j < i*i; j++)       // Runs O(n) times
    {
      if (j % i == 0)                 // Runs O(n) × O(n^2) = O(n^3) times
        {
          for (int k = 0; k < j; k++) // Runs O(n) × O(n) = O(n^2) times
            {
              sum++;                  // Runs O(n^2) × O(n^2) = O(n^4) times
            }
        }
    }
}

这篇关于带if语句的嵌套for循环的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！