时间戳

首页 > 解决方案 > 多个条件的for循环的时间复杂度是多少

algorithm - 多个条件的for循环的时间复杂度是多少

问题描述

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

    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 时遇到了问题，因为我从来没有处理过这么多条件的循环。我已经阅读了这个和这个，但仍然不太正确。据我了解，时间复杂度将是 O(n+m)。其中 n 是 [arr.length]，m 是 [len]，它是上述函数 getArrayMaxLength 的输出。

所以总结一下。算法的时间复杂度是多少？谢谢你。

标签： algorithm

解决方案

请注意，每次 for 循环到达内部数组的末尾时，计数器（变量i）都会重置并且您增加x，传递到下一个内部数组。这意味着您将遍历二维数组的每一个元素，程序输出证实了这一点。

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

总之，时间复杂度为O(n*m)。

推荐阅读