时间戳

首页 > 解决方案 > 使用 mod 操作时如何计算时间复杂度

algorithm - 使用 mod 操作时如何计算时间复杂度

问题描述

我正在尝试查找以下代码的时间复杂度。

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 将仅允许 (N/D) 操作来完成代码 OP[3-6]。

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

这个对吗？

标签： algorithmtime-complexitycomplexity-theory

解决方案

这取决于 V 和 D 的性质，但您的整体时间复杂度分析是正确的，您的结论可能是 O(VN^2/D^2) 或 O(N^2)，具体取决于您如何看待 V 和D 和问题/问题的性质。

推荐阅读