Рубрики

ВОРОТА | Gate IT 2005 | Вопрос 15

В следующей таблице левый столбец содержит имена стандартных алгоритмов графов, а правый столбец содержит временные сложности алгоритмов. Сопоставьте каждый алгоритм с его временной сложностью.

 1. Bellman-Ford algorithm
2. Kruskal’s algorithm
3. Floyd-Warshall algorithm
4. Topological sorting
 A : O ( m log n)
B : O (n3)
C : O (nm)
D : O (n + m)

(A) 1 → C, 2 → A, 3 → B, 4 → D
(B) 1 → B, 2 → D, 3 → C, 4 → A
(C) 1 → C, 2 → D, 3 → A, 4 → B
(D) 1 → B, 2 → A, 3 → C, 4 → D

Ответ: (А)
Объяснение:

  • Алгоритм Беллмана-Форда : временная сложность: O (VE)
  • Алгоритм Крускала : Сложность времени: O (ElogE) или O (ElogV). Сортировка ребер занимает O (ELogE) время. После сортировки мы перебираем все ребра и применяем алгоритм find-union. Операции поиска и объединения могут занимать не более O (LogV) времени. Таким образом, общая сложность составляет O (ELogE + ELogV) время. Значение E может быть не более V ^ 2, поэтому O (LogV) равны O (LogE). Следовательно, общая сложность времени составляет O (ElogE) или O (ElogV)
  • Алгоритм Флойда-Варшалла : Сложность времени : O (V ^ 3)
  • Топологическая сортировка : сложность времени: приведенный выше алгоритм — просто DFS с дополнительным стеком. Таким образом, сложность времени такая же, как и у DFS, которая равна O (V + E).

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | Gate IT 2005 | Вопрос 15

0.00 (0%) 0 votes