用大O计算时间复杂度

我有一个任务，我不确定;我要计算下面的代码的时间复杂度：用大O计算时间复杂度

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（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 2 logn）时间+ O（N 2 ）/ 2）
= O（N 2 logn）时间

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

来源

2016-10-05 RVER12321312

该日志是错误的。完整的复杂性只是二次的。（假设模数不变，if就是一个常量运算） – sascha

@sascha它不是二次的。 – xenteros

@sascha哦，我明白了......我在笔记里的某个地方讲过我的讲师，因为变量有可能是％2，并且出于某种原因它是o（logn）。由于 – RVER12321312

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)。

来源

2016-10-05 15:06:32 xenteros

您正在向橙子添加苹果。你不能告诉'int a [] [] = new int [m] [n];'是'O（1）'而'for（int i = 0; i zerkms

@zerkms我同意。它是'O（mn）'。没有考虑初始化。 – xenteros

不仅如此 - 我的观点是你不能简单地将'O（）'近似值加在一起。简单的理由：你为什么假设'new int [m] [n]'是固定时间？ – zerkms

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)

来源

2016-10-05 15:01:25

所以o（m）和o（n）变量应该被独立处理，而不是o（n^2）来运行for循环两次？ – RVER12321312

如果for循环运行两次（每次最多n次），则会有两个独立的O（n）计算（考虑它是一个循环内的循环）。 O（n）为外环，O（n）为内环，导致O（n^2）。 –

但是，如果它是两个单独的for循环，每个运行到n，那么它将是O（n）+ O（n）= O（2n），这与O（n）相同 –

-1

最终的复杂度为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）。此外，通常您不会考虑在时间复杂性问题中初始化变量。

来源

2016-10-05 15:04:22 PrestonM

错误！第一个循环直到m，而不是n！ –

@ValentinMontmirail它是相同的功能类。 – sascha

这个答案错了吗？ http://stackoverflow.com/questions/362059/what-is-the-big-o-of-a-nested-loop-where-number-of-iterations-in-the-inner-loop – PrestonM

用大O计算时间复杂度

回答

相关问题