时间复杂度O(ab)与O(N²)的区别及代码实例疑问

1. 两层同数组嵌套循环的O(n²)复杂度 #

你说的没错，这段代码确实是**O(n²)**的典型案例：

for (int i = 0; i < array.length; i++) 
    for (int j = 0; j < array.length; j++) 
             System.out.println(array[i] + "," + array[j]); 

两层嵌套循环都遍历长度为n的数组，总执行次数是n * n，对应时间复杂度O(n²)。

2. 两层不同数组嵌套循环的O(ab)复杂度 #

这段代码的时间复杂度标注为**O(ab)**是完全正确的：

for (int i = 0; i < arrayA.length; i++) 
   for (int j = 0; j < arrayB.length; j++) 
       if (arrayA[i] < arrayS[j]) 
           System.out.println(arrayA[i] + arrayB[j]); 

这里arrayA的长度是a，arrayB的长度是b，外层循环执行a次，每一次外层循环都会触发b次内层循环——不管内层的if判断是常数操作（确实可以忽略），循环的总迭代次数是a * b次。O(n²)其实是O(ab)的特殊情况，当a = b = n时，O(ab)就变成了O(n²)，两者本质是同一类复杂度，只是输入规模的变量名不同而已。

3. 含固定次数第三层循环的O(ab)复杂度 #

这段三层循环的时间复杂度确实是O(ab)：

for (int i = 0; i < arrayA.length; i++)
       for (int j = 0; j < arrayB.length; j++)
          for (int k = 0; k < 160800; k++) 
             System.out.println(arrayA[i] + "," + arrayB[j]);

大O表示法的核心是描述复杂度随输入规模增长的趋势，会忽略固定的常数系数。这里第三层循环的次数160800是固定不变的常数，总执行次数是a * b * 160800，当a和b增长时，常数160800对增长趋势没有影响，所以可以直接去掉，最终复杂度就是O(ab)。

内容的提问来源于stack exchange，提问作者rogawiv352