algorithm - 每次迭代循环变量变化时的复杂性？

Question

A(q, cList){                 
    for(i=1;i<q;i++){       // q is the number of keywords in the query
        B(cList[i]);            
    }
}

B(c){
    for(j=1; j<c;j++){  // c specifies how many times the keyword is included, and taken as input
        do something
    }
}

For example: 
A(2, [5, 7])     // 2 keywords are searched, that are included in 5 and 7 documents
A(2, [100, 1500]) // 2 keywords are searched, that are included in 100 and 1500 documents
A(3, [1, 10000, 1500]) // 3 keywords are searched, that are included in 1, 10000 and 1500 documents

外层循环依赖于q。但是我不决定B的复杂度？

c 的值对于每个关键字都会发生变化。我认为这也取决于 c 值。

那么，A的复杂度是多少？

Answer 1

这里我们有 2 个输入增加了复杂性，例如，输入 A(2,[1,100]) .外循环迭代将由函数的第一个参数决定 A ，这里是 2，我们称它为 n至于函数 B 中的第二个循环它的迭代次数将由函数 A 的第二个参数决定在这种情况下，即 [1,100] .通过这些，我们可以通过 O( n * max(cList[])) 来计算最坏情况的复杂度。这里的 max 取 cList 中最长元素的长度.

我本来打算称这种复杂性分析过于悲观，但当我们渐近地思考时，您的运行时间将主要受到 cList 中最大值的影响。 .