Основы программирования на C#



              

Рекурсия - часть 3


Предположим для простоты, что n задается степенью числа 2, то есть n = 2k. Тогда наше соотношение имеет вид:

T(2k) = 2T(2k-1) + c2k

Полагая, что T(1) =c, путем несложных преобразований, используя индукцию, можно получить окончательный результат:

T(2k) = c*k*2k = c*n*log(n)

Известно, что это - лучшее по порядку время решения задачи сортировки. Когда исходную задачу удается разделить на подзадачи одинаковой размерности, то, при условии существования линейного алгоритма слияния, рекурсивный алгоритм имеет аналогичный порядок сложности. К сожалению, не всегда удается исходную задачу разбить на k подзадач одинаковой размерности n/k. Часто такое разбиение не представляется возможным.

on_load_lecture()

Дальше »

  Если Вы заметили ошибку - сообщите нам.  

Страницы:

« |

1

|

2

|

3

|

4

|

5

|

вопросы | »

|

учебники

|

для печати и PDA

Курсы | Учебные программы | Учебники | Новости | Форум | Помощь



Телефон: +7 (495) 253-9312, 253-9313, факс: +7 (495) 253-9310, email: info@intuit.ru

© 2003-2007, INTUIT.ru::Интернет-Университет Информационных Технологий - дистанционное образование




Содержание  Назад  Вперед