Пример 1. Анализ временной сложности:
Граф после удаления:
Анализ временной сложности: Используя формулу 1, а так же с учётом того, что M = 38,
626 проходов по циклам. Анализ ёмкостной сложности: В данном примере количество дуг M = 38, количество вершин N = 17. Теперь рассчитаем ёмкостную сложность для данного примера:
961 байт памяти. Результаты работы программы:
|
16, N = 17, степень исхода вершины 1: 3, степень исхода вершины 2: 2, степень исхода вершины 3: 4, степень исхода вершины 4: 1, степень исхода вершины 5: 2, степень исхода вершины 6: 2, степень исхода вершины 7: 2, степень исхода вершины 8: 1, степень исхода вершины 9: 2, степень исхода вершины 10: 6, степень исхода вершины 11: 3, степень исхода вершины 12: 2, степень исхода вершины 13: 1, степень исхода вершины 14: 1, степень исхода вершины 15: 1, степень исхода вершины 16: 1, степень исхода вершины 17: 4, получим:
