多条件for循环的时间复杂度是多少 [英] What is time complexity of for loop of multiple conditions

问题描述

我试图开发一种解决方案，将 O(n^2) 或 O(n*m) 算法的时间复杂度降低到 O(n) 或 O(n+m) 算法.例如:

I was trying to develop a solution to decrease the time complexity of O(n^2) or O(n*m) algorithm to O(n) or O(n+m) algorithm. For example:

    let arr = [[1, 2], [1, 2, 3], [1, 2, 3, 4, 5, 6, 7, 8]];
    let x = 0;
    let len = getArrayMaxLength (arr) //Get the maximum length of a 2d array which in this example is 8.
    for (let i = 0; i < len && x < arr.length; ++i) {
        print (arr [x][(i % arr [x].length);
        if ((i + 1) % arr [x].length == 0) {
          ++x;
          if (x != arr.length) i = -1;
        }
    }

我在确定这个算法的 Big-O 时遇到了问题，因为我从来没有处理过那么多具有多个条件的循环.我已经阅读了 this 和 this 仍然不完全正确.据我了解，时间复杂度为 O(n+m).其中 n 是 [arr.length]，m 是 [len]，这是上述函数 getArrayMaxLength 的输出.

I'm having problem to determine the Big-O of this algorithm as i have never dealt with loop with multiple conditions that much. I've read this and this and still don't get quite right. From what i understand the time-complexity will be O(n+m). Where n is [arr.length] and m is [len] which is the output of a function getArrayMaxLength as described above.

总结一下.算法的时间复杂度是多少?谢谢.

So to sum things up. What is the time complexity of the algorithm? Thank you.

推荐答案

请注意，每次 for 循环到达内部数组的末尾时，计数器(变量 i)都会重置，并且您会增加 x，传递到下一个内部数组.这意味着您要遍历二维数组的每个元素，程序输出会确认这些元素.

Note that every time the for loop reaches the end of an inner array, the counter (variable i) resets and you increase x, passing onto the next inner array. That means you go through every single element of your two-dimensional array, which the program output confirms.

尽管 n+m 复杂性看起来不错，但实际上是一个糟糕的近似值.实际上，由于数组长度不同，复杂性总是更大.假设所有子数组的长度相同，所以 n = m.当您为 n 个内部数组中的每一个访问 n 个元素时，总复杂度将是二次的 (n*n) 而不是线性的.当您使用大型阵列时，这种差异变得非常明显.

Although n+m complexity may seem ok, it is actually a bad approximation. In practice, the complexity is always bigger because array lengths vary. Imagine that all the subarrays have the same length, so n = m. As you visit n elements for every of the n inner arrays, the total complexity would then be quadratic (n*n) and not linear. When you're working with big arrays this difference becomes very obvious.

总之，时间复杂度是O(n*m).

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