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

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

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

不,根据定义它是O(n ^ 2)[这里解释太久了,但请相信我( – :]
但是你可以减少一半的迭代次数:

 for (i=0; i 

您可能会做一些事情,但这些事情是可能的,并且不依赖于arrays性质和您应用的公式。 总体复杂性可能保持不变甚至增长,即使计算速度更快,除非公式具有复杂性依赖于其参数,在这种情况下可以实现复杂性的降低。

此外,如果B远小于A,则从AO(N ^ a)到BO(N ^ b) ,b> a (更高的复杂度)仍然值得追求,对于某些N的范围。

没有特别的顺序:

  • 如果矩阵有多个重复项,则可以方便地使用缓存function:

    结果函数(arg1,arg2){int i = index(arg1,arg2); //取决于值,它可能是//类似于arg1 *(MAX_ARG2 + 1)+ arg2; if(!stored [i]){//存储和值被分配并初始化//在其他地方 – 或在此函数中使用//静态标志。 stored [i] = 1; values [i] = true_function(arg1,arg2); } return values [i]; }

    然后,您的内存开销与可用的不同值对的数量成比例。 调用开销可以是O(| arg1 | * | arg2 |),但在某些情况下(例如, true_function()很昂贵),节省的成本将抵消增加的复杂性。

    • 将配方切成碎片( 每种配方不可能)并表达为:

      F(x,y)= G(x)op H(y)op 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中是迭代的)。

不,如果您包含数组内容的知识,以及优化算法的操作语义,则只能降低计算复杂度。