0 
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的复杂度是多少？

4

1 回答 1

1

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

我打算将这种复杂性分析称为过于悲观，但是当我们渐近地认为您的运行时间将主要受cList.

于 2018-08-06T11:52:00.470 回答