时间戳

首页 > 解决方案 > 遍历 3D 数组的算法复杂度

arrays - 遍历 3D 数组的算法复杂度

问题描述

我有一个遍历 3d 数组的算法。对于数组中的每个值，我都会进行一些计算。我试图弄清楚算法的时间复杂度。就我而言，这不是一个完整的遍历，不考虑数组的某些值。

def process_matrix(k: int, V: int):
    import numpy as np
    sp_matrix = np.zeros((V, V, k))
                
    for e in range(k):
        for i in range(V):
            # Note that the range of index j decreases while index i is growing 
            for j in range(i, V):
                # Also the index a decreases acording to index i
                for a in range(i, V):
        
                    if (something):
                        sp_matrix[i][j][e] = set_some_value()

如您所见，我没有考虑每个索引 e 的值 j < i。如果我们只采用最外层的三个循环，我认为复杂度是：

V * (1+V)/2 * k

k -> 最外层循环

V*(1+V)/2 -> 对于第二个和第三个循环，我使用高斯公式来添加连续数字

通过一些近似，我认为这三个循环的复杂性是O(((V^2)/2)*k)。

首先，我认为内循环对O有另一个 (1+V)/2 的贡献。结果为 (V * (1+V)/2 * k) * (1+V)/2。但后来我考虑了这种情况：
k = 1
V = 3
结果数组是：

        j=0   j=1   j=2 
    i=0 | 3 | 3 | 3 |       
    我=1 | x | 2 | 2 | 
    我=2 | x | x | 1 |
    （矩阵中的值表示最内层循环..循环的次数）

总数是：3+3+3+2+2+1 = 14
我希望使用我的公式 (V * (1+V)/2 * k) * (1+V)/2,
(3* (1+3)/2*1) * (1+3)/2 = 12
但不是...

标签： arraysalgorithmmatrixtime-complexitybig-o

解决方案

Big-O 表示法是关于设置上限，忽略常数因素。从这个意义上说，考虑到 3 个外部循环，O(((V^2)/2)*k) = O(k * V^2)和 ifk是常数，= O(V^2)。

但是，如果您开始计算最内层代码的执行次数，并将这些执行次数与您的预期执行次数进行比较，那么您将离开大 O 领域，因为不能再忽略常量因素。此外，计算单个指令的执行次数虽然有用，但并不像测量实际性能那样精确（但是，这将取决于您测试它的确切工作负载和机器/环境）。

由于您的 3 个内部循环本质上是在绘制一个四面体，因此您可以使用它的公式来获得复杂度的近似值：O(V^3 / 3)。但是，如果你想得到准确，我已经成功地测试了以下 JS 代码：

let K=1, V=6, t=0;  // t is for counting totals; reset to 0 for each try
for (let k=0; k<K; k++)               // inside repeats K times
    for (let i=0; i<V; i++)           // inside repeats V*K times
        for (let j=i; j<V; j++)       // inside repeats (V+1)*(V) / 2 * K times
            for (let a=i; a<V; a++)   // inside repeats (V+1)*(V+.5)* V / 3 * K times
                console.log(k,i,j,a,++t, (V+1)*(V+.5)* V / 3 * K);

推荐阅读