ажливими при аналізі трудомісткості. Це функції Create_Tree де ми створюємо дерево в залежності від ваги символів і функція Coding_Tree. Почнемо з оцінки цих функцій. p align="justify"> У функції Create_Tree ми використовуємо цикл В«поки розмір вектора НЕ дорівнює 1В», отже, цикл виконується N-1 раз. Звідси можна припустити що складність функції буде O (N), тобто змінюється лінійно. Однак у циклі викликається функція Sort, тому потрібно розрахувати і складність цієї функції. p align="justify"> Функція Sort являє собою сортування вектора Tree_vector, а точніше елементів усередині нього по параметру weight (вага). Сортування представляє собою поліпшений метод бульбашки. Тобто цикл управляє прапорцем repeat і отже кількість проходів циклу буде менше, ніж при статичному методі бульбашці, де виконується вкладений цикл. Таким чином, отримуємо, що в В«кращомуВ» випадку цикл виконається N раз, а в В«гіршомуВ» випадку він виконається N2 разів. У такій ситуації ми дивимося на В«найгіршийВ» випадок і приймаємо складність функції Sort як O (N2). p align="justify"> У підсумку, т.к. функція Sort викликається усередині функції Create_Tree, щоб отримати загальну складність функції нам необхідно перемножити O (N) і O (N2). Таким чином, складність функції Create_Tree складе O (N3). p align="justify"> Слід зауважити, що складність алгоритму Гоффмана (у загальному випадку) вважається рівною O (N * log (N)), де перший множник - кількість проходів по циклу (основний цикл) і отже його складність, а другий (log (N)) - складність сортування елементів за їх вагою (частоті). Тобто в даній програмі функція Sort реалізована В«неідеальноВ», звідси виходить різна складність алгоритму в теорії і на практиці.
Перейдемо до функції Coding_Tree. Тут представлена ​​рекурсивна функція обходу бінарного дерева. Процедура додавання об'єкта в бінарне дерево має середню алгоритмічну складність порядку O (log (N)). Відповідно, для N об'єктів складність становитиме O (N * log (N)). У нашому випадку ми шукаємо листя дерева без В«синівВ». Причому при знаходженні цього листа ми в циклі шукаємо символ у векторі символів і присвоюємо йому код. Цикл виконується N раз (статично). Порахуємо загальну складність функції Coding_Tree:
((N * log (N)) + O (N) = O (N * (log (N) +1)) = O (N * log (N))
програма алгоритм кодування Хаффман
Звідси маємо, що трудомісткість алгоритму становить O (N3) + O (N * log (N)).
Це трудомісткість самого алгоритму Гоффмана, реалізованого в програмі. Але програма складається з великих частин, ніж сам розрахунок. Для практики расчитаем загальну складність всієї програми:
Функція Read_File має складність O (N2), тому що в ній викликається функція Find_this_symbol що має складність O (N), тому що вона в В«гіршому випадкуВ» проходить по всіх N елементів, а сама функція Read_File також має скла...
