algorithm - 算法的大O

Question

我对这个算法有疑问，我很难理解它的复杂性

    While(input) {
            ...
            array to check 
            ...
           for (int i=0; i< arraysize; i++) {  
                creation first subarray; 
                creation second subarray; 
           } 

           for (int i=0; i < firstsubarraysize; i++) {
                 addinput to array;
                for( int j = 0; j < secondsubarraysize; j++) {
                   calculate array[j] * input;
             }
           }
   }// endwhile

那么，考虑输入一个 M 变量并且数组是 N，大 O 将是 O(m(nlogn)) 或 O(n2)？子数组并不总是 n\2。如果我不是很清楚，我深表歉意。

Answer 1

通常，对于每个嵌套循环，时间复杂度的大 O 中会有一个 N。

这里假设最外层的循环while运行了M次，那么里面有两个嵌套的for。所以总数是 O(M N^2)。