упінь результату вершини 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, отримаємо: В
проходів по циклах.
Аналіз ємнісний складності:
У даному прикладі кількість дуг M = 38, кількість вершин N = 17. Тепер розрахуємо ємнісну складність для даного прикладу:
В
байт пам'яті.
Результати роботи програми:
В В В В
Приклад 2
Вихідний граф:
В
Граф після видалення:
В
Аналіз тимчасової складності:
Для обчислення кількості проходів по циклах скористаємося формулою 1:
В
проходів по циклах.
Аналіз ємнісний складності:
У даному прикладі кількість дуг M = 65, кількість вершин N = 31. Виходячи з цього, розрахуємо ємнісну складність:
В
байт пам'яті.
Результати роботи програми:
В В В В В В
Приклад 3
Вихідний граф:
В
Граф після видалення:
В
Аналіз тимчасової складності:
Скориставшись формулою 1, розрахуємо тимчасову складність програми для даного прикладу (кількість дуг M = 181,, N = 77):
В
прохід по циклах.
Аналіз ємнісний складності:
У даному прикладі кількість дуг M = 181, кількість вершин N = 77. Виходячи з цього, обчислимо ємнісну складність програми для даного прикладу за формулою 2:
В
байт пам'яті.
Результати роботи програми:
В В В В В В
В В
4. Вихідний код програми:
# include "stdafx.h"
# include
# include
# include
# include namespace std; ArcGraph {outVertexId; inVertexId;
}; DirectedGraph {oneArc; * previousArc; * nextArc;
}; _input (int & var) {BAD_STATE = 2; {. clear ();. sync ();>> var;
} while (cin.rdstate () == BAD_STATE);
} _input (char & output, char mode = 'b') {char OUTPUT_MODE = 'o', ASK_MODE = 'b', MAIN_MODE = 'm', SOME_ACTIONS_MODE = 's'; successfulInput ; {. sync ();>> output; (output == 'e') exit (0); (mode) {OUTPUT_MODE: successfulInput = (output == 'f' | | output == 's') ; break; ASK_MODE: successfulInput = (output == 'y' | | output == 'n'); break; MAIN_MODE: successfulInput = (output == 'p' | | output == 'm' | | output == 'd' | | o...
