Сложность времени и сложность пространства

Мой алгоритм показан ниже. Он делает удаленный вызов на сервер и получает результаты, обрабатывает их и снова отправляет удаленный вызов в систему. Можете ли вы дать мне представление о том, какова может быть временная и пространственная сложность этого алгоритма?

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

person Edi 0    schedule 18.08.2012    source источник
comment
Можете ли вы правильно сделать отступ для циклов? Я не могу понять отступ даже в исходном сообщении. Я только редактирую его, чтобы удалить лишние пробелы, чтобы его было легче читать.   -  person nhahtdh    schedule 18.08.2012


Ответы (1)


Ваш второй цикл вложен в первый? Если да, приведенный ниже анализ сложности соответствует вашему алгоритму.

Временная и пространственная сложность этого алгоритма зависит от реализации функций expandConcept(), getKeywords(), add() и performsearch(). Для add() временная и пространственная сложность может быть O(1), если просто добавить свой аргумент к переднему индексу массива expConcepts. Предположим, что performsearch() выполняет бинарный поиск, который имеет O(logN) (N: количество элементов expConcepts), временную сложность и постоянную пространственную сложность, а также дополнительные O(M*(expandConcept() time-comp)*K*(expandConcept() time-comp)) (M: кардинальное число набора e, K: кардинальное число ключевых слов), у вас есть O(M*(expandConcept time-comp)*K*(expandConcept() time-comp)*logN) временная сложность. Сложность пространства зависит от expandConcepts() сложности пространства.

person Kapoios    schedule 18.08.2012