所有数组元素的比较 - C算法

Question

我有一个矩阵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
        }
    }
}

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

Answer 1

不，根据定义，它是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)
        }
    }
}