Класс. МУПР ОП.08 Теория алгоритмов. Методические указания по проведению практических работ по дисциплине Теория алгоритмов

• Название: Методические указания по проведению практических работ по дисциплине Теория алгоритмов
• Анкор: Класс
• Дата: 14.11.2019
• Размер: 3.39 Mb.
• Имя файла: МУПР ОП.08 Теория алгоритмов.doc
• Тип: Методические указания; #95109
• страница: 27 из 29

n на n/4, получаем оценку для T(n/4): T(n/4)2T(n/8)+c2*n/4. Подставим эту оценку в (7.3) и получим такое выражение:

(7.4)

Проанализировав характер изменения T(n) преобразуем (7.1) к виду:

(7.5)

Предположим, что , тогда при i=k в правой части (7.5) находится T(1):

(7.6)

Так как , то ,а T(1)c1, то (7.6) можно преобразовать

. (7.7)

Неравенство (7.7) демонстрирует верхнюю границу для T(n), а порядок роста T(n) не более O(nlogn).