当使用mod操作时，如何计算时间复杂度？

Question

我试图找到以下代码的时间复杂度。

N= number of elements in array
D= a constant: D>1
V= a constant: V>1000

counter=1; //the maximum value of the counter is N/D.
for(i=0; i<N; i++)
{
    [OP1]   O1_Operation;        // O(1) operation.   [Total: N times]
    [OP2]   if(i%D!=0) continue; // O(1) operation.   [Total: N times]

    [OP3]   for(j=0;j<counter;j++) //                 [Total: {(N/D)*((N/D)+1)}/2 times] 
    [OP4]        for(s=0;s<V;s++)
    [OP5]            O1_Operation; // O(1) operation. [Total: (V*{(N/D)*((N/D)+1)}/2) times] 

    [OP6]   counter++;             // O(1) operation. [Total: N/D times]
 }

我添加了每个操作的时间复杂度和它将被执行的总次数。在这段代码中，我感到困惑的是mod操作。这个mod只允许(ND)操作来完成代码OP[3-6]。

对于[OP3]，第一次会被执行1次，第二次会被执行2次，...，ND次。因此，总的执行次数可以是[(ND) * ( (ND)+1)] 2。去掉D和V，因为它们是常数，会导致整个代码的复杂度为O(N^2)。

这是否正确？

Answer 1

这取决于V和D的性质，但你的总体时间复杂度分析是正确的，你的结论可能是O(VN^2D^2)，也可能是O(N^2)，这取决于你如何看待V和D以及问题question的性质。