» число виходить з розрахунку 110 В» 2 16 /3 . Це відбувається тому, що стандартний тип int не може вмістити в себе більш ніж 2 16 . Мені ж потрібно для нормально роботи програми, щоб тип вміщував в себе утроенное кількість вершин неорієнтованого графа. Звичайно, це всього лише наближення, але з урахуванням того, що графи генеруються випадково можливість набору 33000 невелике і, отже, припустимо.
Вхідний файл генерується щоразу новий.
Графи для розрахунку мультиплікативних констант генеруються випадковим чином, використовуючи датчик випадкових чисел, це-то і накладає обмеження на кількість вершин. Справа в тому, що при роботі з генератором випадкових чисел предпостітельно іоспользовать цілий тип даних - так говорив товариш Подбельський В.В.
В В В В В В В В В В В В В В В В В В В В В В В В В
Оцінка тимчасової складності.
В
ковзанці відомості про тимчасову складності.
В
Якість алгоритму оцінюється як точність рішення і ефективність алгоритму, яка визначається тим часом, який витрачається для вирішення завдання і необхідним обсягом пам'яті машини.
Тимчасова складність алгоритму є залежність від кількості виконуваних елементарних операцій як функція розмірності задачі. Тимчасова складність алгоритму А позначається.
Розмірність завдання - це сукупність параметрів, що визначають міру вихідних даних. Тимчасова оцінка алгоритму буває двох типів:
1. апріорна - асимптотическая оцінка складності
2. апосторіорная - оцінка складності алгоритму з точністю до мультиплікативних констант, зроблених для конкретної машини.
Саме асимптотическая оцінка алгоритму визначає результаті розмірність задачі, яку можна вирішити за допомогою ЕОМ. Якщо алгоритм обробляє вхідні дані розміру N за час CN 2 , де З - якась постійна, то говорять, що тимчасова складність цього алгоритму є. Вірніше говорити, що позитивна і нульова функція є, якщо існує така постійна З , що для всіх негативних значень N .
В
Обчислення тимчасової складності.
Для того, щоб перевірити правильність тимчасової оцінки алгоритму, треба знати апріорну оцінку складності.
Перевірка обчислювальної складності алгоритму зводитися до експериментального порівнянні двох або більше алгоритмів, вирішальних одну і ту ж задачу. При цьому виникають дві головні проблеми: вибір вхідних даних і перекладу результатів експерименту в графіки кривих складності.
При прогоні програми ми отримуємо значення функції, які можна зобразити на графіку як функцію f (
