javascript - 在一个循环中编写的 2 for 循环的时间复杂度是多少

Question

嗨，我只是在想，如果我像下面给出的那样编写 for 循环，它的时间复杂度是多少。它将 o(n^2) 或只是 o(n)

for(var i=0,j=0;i<arr1.length || j<arr2.length;i++,j++)
{
    //some code here
}

标签： javascriptfor-looptime-complexity

Answer 1

时间复杂度为O(max(m, n))，其中m和narr1分别是和的大小arr2。

在您的for循环中，您在循环之后i和j之后都增加。如果和 ，则for循环停止。由于和总是具有相同的值（除了增量和之间的时刻），因此如果两者和都到达其对应列表的末尾，则它会结束。i >= arr1.lengthj >= arr2.lengthijijij

我们在这里假设递增i并j在恒定时间内运行（对于非常大的数字，这将采用O(b)和b任意大小的数字的位数），并且循环的主体仅包含指令for也以恒定的时间运行。