1

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

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
4

1 回答 1

1

你的第二个循环嵌套到第一个?如果是,下面给出的复杂性分析代表您的算法。

该算法的时间和空间复杂度取决于expandConcept()getKeywords()和函数的实现。对于,时间和空间复杂度可能是如果只是将其参数附加到 expConcepts 数组的前索引。假设执行二分搜索,它具有(:expConcepts 元素的数量)、时间复杂度和恒定空间复杂度,以及额外的(:集合 e 的基数,:akeywords 的基数),您就有时间复杂度。空间复杂度取决于空间复杂度。add()performsearch()add()O(1)performsearch()O(logN)NO(M*(expandConcept() time-comp)*K*(expandConcept() time-comp))MKO(M*(expandConcept time-comp)*K*(expandConcept() time-comp)*logN)expandConcepts()

于 2012-08-18T15:47:42.370 回答