大O计算时间复杂度

Question

我有一个作业我不确定；我必须计算以下代码的时间复杂度：

int a[][] = new int[m][n];        //O(1)
int w = 0;                        //O(1)
for (int i = 0; i < m; i++)       //O(n)
    for (int j = 0; j <n; j++)    //O(n)
         if (a[i] [j] % 2 == 0)   //O(logn)
         w++;                     //O(1)

所以根据我的 O 估计，我将它们加起来：

O(1) + O(1) + O(n) * ( O(n) * ( O(logn) + O(1) / 2 ) )
O(1) + O(1) + O(n) * ( O(nlogn) + O(n) / 2 )
O(1) + O(1) + (O(n²logn) + O(n²) / 2)
=O(n²logn)

我不确定我的思路是否正确，有人可以帮忙吗？

Answer 1

 for (int i = 0; i < m; i++)  //O(m)
  {   
    for (int j = 0; j <n; j++) //O(n)
    {
      // your code
    }
  }

因此第 i 个循环将进行 m 次，第 j 个循环将运行 n 次。因此，代码总共将执行 m*n 次，这就是它的时间复杂度：O(m.n)

Answer 2

最终复杂度为O(n^2)

你的逻辑很接近，除了...

int a[][] = new int[m][n];        //O(1)
int w = 0;                        //O(1)
for (int i = 0; i < m; i++)       //O(n)
    for (int j = 0; j <n; j++)    //O(n)
         if (a[i] [j] % 2 == 0)   //O(1)
         w++;                     //O(1)

第二个 for 循环中嵌入的 if 语句只是引用数组中的元素并进行基本比较。这是时间复杂度 O(1)。此外，通常您不会考虑在时间复杂度问题中初始化变量。

Answer 3

for (int i = 0; i < m; i++)       //O(m)
    for (int j = 0; j <n; j++)    //O(n)
         if (a[i] [j] % 2 == 0)   //O(1)
         w++;                     //O(1)

所以 big-o 的总复杂度是：

O(m)*(O(n) + O(1) + O(1)) = O(m)*O(n) = O(m*n).

大O计算时间复杂度

Calculating time complexity with big O

algorithm

math

big-o

time-complexity