Алгоритм TextRank Пространство и временная сложность

Question

Я пытаюсь определить пространственно-временную сложность для TextRank алгоритма, указанного в этой статье: https://web.eecs.umich.edu/~mihalcea/papers/mihalcea.emnlp04.pdf

Поскольку он использует PageRank, сложность которого: O (n + m) (n - количество узлов, m - количество дуг / ребер) и мы запускаем его за i итераций / до сходимости сложности для извлечения ключевых слов, я думаю, что это будет: O (i * (n + m)) и сложность пространства будет O (V ^ 2) с использованием матрицы смежности

Хотя для извлечения предложения я думаю, что это было бы то же самое.

Я действительно не уверен, и любая помощь будет отличной. Спасибо.

Answer 1

Если вы повторите T раз алгоритм ( внутренний ) со сложностью O (n + m) или любым другим по этому вопросу, будет правильным сделать вывод, что новый алгоритм ( внешний ) будет иметь сложность O (T * (n + m)) при условии:

1. Внешний алгоритм добавляет постоянную сложность только каждый раз, когда повторяет внутренний.
2. Параметры n и m остаются неизменными при каждом вызове внутреннего алгоритма.

Другими словами, внешний алгоритм должен подготавливать входные данные для внутреннего за постоянное время, а параметры новых входных данных должны оставаться хорошо представленными n и m на протяжении T итераций. В противном случае, если какое-либо из этих двух требований не будет доказано, вы должны сложить T раз сложности, связанные с новыми параметрами, скажем

O(n1 + m1) + ... + O(n_T + m_T)

, а также принимать во внимание всю предварительную и последующую обработку внешнего алгоритма до и после использования внутреннего.