我不太确定我的算法的大 O 是 O(n^3) 还是 O( m * n * n )

Question

所以，我试图在下面找到我的算法的大 O。

for(int x=0;x<m;x++){
    for(int y=0;y<n;y++){
        for(int z=0;z<n;z++){
            if(target[x][y]==source[z]) count++;
        }
    }
}

但是，我不太确定是 O(n^3) 还是 O( m * n * n )...

Answer 1

在我看来它是 O(m*n*n)，也就是 O(m*n²)，因为你的外循环遍历 m，但是你的两个内循环各自遍历 n.

Answer 2

除了嵌套之外，每个循环都独立于其他循环，因此它是每个循环次数的简单乘法：O(m * n * n) = O(m * n² ).

这意味着性能将随着 m 的增加呈线性增长，并随着 n 的增长呈二次方增长。如果两者都增加，性能将按其乘积扩展。

除非 m 和 n 之间存在某种未说明的关系，否则不能将其概括为 O(n³)。恰恰相反，如果没有关系，您甚至可以考虑算法 O(m)（如果您对缩放 n 时发生的情况不感兴趣）或 O(n²)（如果您对缩放 m 时发生的情况不感兴趣）。

---

注意这种查找可以在O(m + n²).

1. 创建一组。
2. 对于 source 的每个 m 个元素，
   1. 让我们调用s当前元素的值。
   2. 如果集合不包含 s，
      1. 将 s 添加到集合中。
3. 对于target的n*n个元素的每个元素，
   1. 让我们调用v当前元素的值。
   2. 如果集合包含 s，
      1. count加一。

这假设集合查找是 O(1) 并且添加到集合是 O(1)（摊销）。

Answer 3

循环 O(n)。 循环内循环 O(n*n) 或 O(n^2)。 在另一个循环内循环 O(n*n*n) 或 O(n^3).

你的最外层循环是依赖于 n 还是 m？当然你不能像 none.

那样忽略外循环

因此你的三个循环中的 O(m*n*n)。