时间复杂度和空间复杂度

Question

我的算法如下所示。它对服务器进行远程调用，并获取结果、处理结果，然后再次将远程调用发送到系统。你能告诉我这个算法的时间和空间复杂度是多少吗？

Get search keyword from user
ϕ := getInfoFromConceptNet(keyword) // makes remote call
e := expandConcepts(ϕ)
expConcepts := {} // adds to an array
for each ec in e // first loop
expConcepts.add(ec) // adds to array
α= expandConcept(ec) //remote call
expConcepts.add(α) // adds to array
αkeywords=getKeywords(α) // calls a function to remove stopwords
for each αkw in αkeywords // second loop
Ω= expandConcept(αkw) // makes remote call
expConcepts.add(Ω) // adds to an array
results[ ]=performsearch(expConcepts,additional information) // searches the array

Answer 1

你的第二个循环嵌套在first？如果是，下面给出的复杂性分析就是你的算法。

该算法的时间和空间复杂度取决于expandConcept()、getKeywords()、add()和performsearch()函数的实现。对于add()，如果只是将其参数附加到expConcepts数组前索引，则时间和空间复杂度可能为O(1)。假设performsearch()执行二进制搜索，它有一个O(logN) (N：number of expConcepts elements)、时间复杂度和常量空间复杂度，以及一个额外的O(M*(expandConcept() time-comp)*K*(expandConcept() time-comp)) (M：集合e的基数，K：a关键字的基数)，那么就有一个O(M*(expandConcept time-comp)*K*(expandConcept() time-comp)*logN)时间复杂度。空间复杂度取决于expandConcepts()空间复杂度。