дність O (N).
Функція Create_Null_Nodes статична і має складність O (N).
Функція Print_Symbol_Codes має подвійний цикл, і обидва циклу проходять значення від 0 до N, звідси складність всієї функції становить O (N2).
Функція Print_Coded_Text яка являє собою цикл виконується N раз, причому в собі він містить подвійний цикл, аналогічний циклу в попередній функції. Звідси складність всієї функції складе O (N3). p align="justify"> Функція Binary_Writing за будовою аналогічна функції Print_Coded_Text і її трудомісткість складе O (N3).
У функції int main ми послідовно викликаємо всі перераховані функції, тому можемо скласти загальну трудомісткість алгоритму як суму складнощів цих функцій:
(N) + O (N) + O (N3) + O (N * log (N)) + O (N2) + O (N3) + O (N3) =
= 2 * O (N) + O (N2) + 3 * O (N3) + O (N * log (N)) =
= O (N) + O (N2) + O (N3) + O (N * log (N)) = O (N * log (N))
Дана арифметика складається з того, що константи при O (x) не враховуються. А сума вийшла рівною O (N * log (N)), тому що іншим складності мають менше значення, і є занадто незначними.
ВИСНОВОК
Програма представляє собою спрощену версію архіватора, тому що розмір вихідного файлу зменшується приблизно в 2 рази. На прикладі рядки В«Hello, my name is BoxxyВ» ми можемо побачити, що вихідний файл займає 23 байта, а вихідний - 10 байт. На прикладі вірша Тютчева В«Silentium!В» Вихідний файл займає 492 байти, а вихідний 293 байти (майже аналогічне ставлення розмірів). На прикладі першого тому твору «³йна і МирВ» Л.М. Толстого розмір вихідного файлу складає 709 кілобайт, а вихідного - 441 кб. Слід зауважити, що виконання останньої операції витратило близько 8 хвилин, з яких: 2 хвилини виводився вихідний текст, виконання алгоритму Гоффмана та кодування символів зайняло порядку секунди, і решту часу - висновок закодованого файлу на екран (у вигляді нулів і одиниць). Запис у файл також зайняла близько 10 секунд. p align="justify"> Звідси випливає що тимчасові витрати самого алгоритму незначні і не сильно збільшуються з ростом вхідних даних. Найдовше відбувається звернення до диску на читання/запис файлу. p align="justify"> Реалізація самої програми може бути поліпшена в деяких аспектах (краща сортування, переривання циклів замість статичного кількості проходів, спрощення пошуку символів у векторі символів використанням гнучкості мови C + + (наприклад, структура map або list замість vector)), проте на швидкість виконання програми це вплине незначно.
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
1. Лекція № 8 В«Аналіз трудомісткості алгоритмівВ» з курсу В«Математична логіка і теорія алгоритмівВ».
. Статті сайту habraha...
