значення в точках, тобто. Розрядність чисел (відповідно) не перевищує, де - деяка константа, що залежить oт . Ясно, що якщо - складність множення-бітових чисел, то складність множення-бітових чисел є для деякої константи.
Якщо - складність множення-бітових чисел, то справедливо співвідношення (- константа). Звідси і згідно викладеним раніше результатами, отримуємо. Оскільки маємо і, позначаючи можна записати. Таким чином, доведено, для будь-якого існує алгоритм множення-бітових чисел, для якого складність задовольняє співвідношенню.
Є й більш ефективні алгоритми множення чисел, але вони використовують вже не цифрові операції [20]. p> Узагальнюючи отримані результати, потрібно відзначити, що багато поширені і важливі алгоритмічні завдання допускають рекурсивні рішення. Незважаючи на гадану громіздкість (адже на кожному кроці кількість подалгорітма меншої розмірності збільшується в кілька разів) аналіз з використанням апарату теорії складності показує, що вони найчастіше менш трудомісткі, ніж звичайні ітераційні. Однак саме отримання сложностних оцінок не так просто. У більшості випадків функція складності визначається за допомогою рекурентних співвідношень, знаходження явного її виду представляє деякі труднощі. Справитися з цією проблемою вдається при спеціально підібраних значеннях розмірності вихідної задачі. Інші значення вимагають окремого дослідження і зазвичай дозволяють отримати тільки грубі оцінки.
В В В В В В В В В В В В В В В В В В
Програмна реалізація рекурсії.
В
Загальні принципи реалізації.
Раніше було показано, що рекурсія є надзвичайно зручною і корисною алгоритмічної структурою. Рекурсивні алгоритми, як правило, менш складні. Настав час з'ясувати, як використовувати їх у практичній роботі. p> Рекурсивні алгоритми в програмуванні реалізовані в механізмі так званих рекурсивних підпрограм. Рекурсивної вважається підпрограма, яка прямо або побічно, через інші підпрограми, звертається до себе, бути може з іншими фактичними параметрами. У сучасних системах програмування коректне функціонування підпрограм, особливо рекурсивних, забезпечується за допомогою стека.
Стек - зв'язкова структура даних, побудована на принципі В«перший прийшов - перший вийшов В»(First In - First Out, FIFO). Тобто знову додаються об'єкти поміщаються в початок, вершину стека, і вибираються вони також тільки з вершини. p> Стек є надзвичайно зручною структурою даних для багатьох завдань обчислювальної техніки. Найбільш типовою з таких завдань є забезпечення вкладених викликів процедур. Припустимо, є процедура A, яка викликає процедуру B, а та в свою чергу - процедуру C. Коли виконання процедури A дійде до виклику B, процедура A призупиняється і управління передається на вхідну крапку процедури B. Коли B доходить до виклику C, призупиняється B і управління передається на процедуру C. Коли закінчується виконання процедури C, управління повинне...
