5

我有一个矩阵m * n，对于每一行，我需要比较它们之间的所有元素。对于我找到的每一对，我都会调用一个函数来执行一些计算。

例子：

my_array -> {1, 2, 3, 4, 5, ...}

I take 1 and I have: (1,2)(1,3)(1,4)(1,5)
I take 2 and I have: (2,1)(2,3)(2,4)(2,5)
and so on

使用 CI 写道：

for (i=0; i<array_length; i++) {
    for (k=0; k<array_length; k++) {
        if (i==k) continue;

           //Do something
        }
    }
}

我想知道是否可以使用复杂度较低的算法。

4

3 回答 3

5

不，根据定义它是 O(n^2) [这里解释太长了，但相信我 (-: ]
但是你可以将迭代次数减少一半：

for (i=0; i<array_length; i++) {
    for (k=i+1; k<array_length; k++) { // <-- no need to check the values before "i"
           //Do something
           //If the order of i and k make a different then here you should:
           //'Do something' for (i,k) and 'Do something' for (k,i)
        }
    }
}
于 2013-03-28T12:28:45.153 回答
3

您可能会做几件事，但哪些是可能的，哪些不取决于数组性质和您应用的公式。总体复杂性可能会保持不变甚至增加，即使计算可以更快，除非公式的复杂性依赖于它的参数，在这种情况下，复杂性的降低是可以实现的。

此外，如果 B 比 A 足够小，对于某个范围的 N，从 AO(N^a) 到b > a （更高复杂度）的 BO(N^b) 仍然值得追求。

没有特别的顺序：

  • 如果矩阵有多个重复项，使用缓存功能会很方便：

    结果函数(arg1, arg2) { int i = index(arg1, arg2); // 根据值，它可能是 // 类似于 arg1*(MAX_ARG2+1) + arg2; if (!stored[i]) { // 存储和值被分配和初始化 // 在其他地方 - 或者在这个函数中使用 // 静态标志。存储[i] = 1; 值[i] = true_function(arg1, arg2); } 返回值[i]; }

    然后，您的内存开销与可用的不同值对的数量成正比。调用开销可能为 O(|arg1|*|arg2|)，但在某些情况下（例如true_function()昂贵），节省的费用将超过增加的复杂性。

    • 将公式切成小块（并非每个公式都可能）并将其表示为：

      F(x,y) = G(x) 运算 H(y) 运算 J(x,y)

    然后，您可以执行 O(max(M,N)) 循环预先计算 G[] 和 H[]。这也有 O(M+N) 的内存成本。仅当 F 和 J 之间的计算开销差异显着时才方便。或者你可以这样做：

    for (i in 0..N) {
    g = G(array[i]);
    for (j in 0..N) {
        if (i != j) {
            result = f(array[i], array[j], g);
        }
    }
}

    这将一些复杂性从 O(N^2) 降低到 O(N)。

    • 如果 G() 或 H() 可用于缓存（参数范围有限，函数昂贵），则前两种技术可以串联使用。

    • 找到将 F(a, b) 与 F(a+c, b+d) 联系起来的“法则”。然后，您可以更有效地运行缓存算法，重用相同的计算。这将一些复杂性从 O(N^2) 转移到 O(N) 甚至 O(log N)，因此虽然总体成本仍然是二次方，但它的增长要慢得多，并且 N 的更高界限变得实用。如果 F 本身的复杂度比 (a,b) 中的常数高，这也可能会降低这个顺序（作为一个极端的例子，假设 F 在 a 和/或 b 中是迭代的）。

于 2013-03-28T13:36:58.337 回答
2

不，只有包含数组内容的知识以及优化算法的操作语义，才能降低计算复杂度。

于 2013-03-28T12:24:25.993 回答