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

2 番目のループが最初にネストされていますか? はいの場合、以下に示す複雑さの分析は、アルゴリズムを表しています。

このアルゴリズムの時間と空間の複雑さはexpandConcept()、 、getKeywords()add()およびperformsearch()関数の実装によって異なります。の場合、引数を expConcepts 配列のフロント インデックスに追加するだけの場合add()、時間と空間が複雑になる可能性があります。が( : expConcepts 要素の数)、時間の複雑さと一定のスペースの複雑さ、および追加の( : セット e の基数、 : a キーワードの基数)を持つバイナリ検索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 に答える