![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Количество повторений вложенного цикла зависит от параметра внешнего цикла
Введем следующие обозначения: k - количество повторений внешнего цикла. В примере k=n. f(k) – функция зависимости количества повторений вложенного цикла от числа повторений внешнего цикла. В примере f(1)=1, f(2)=2, …, f(n)=n. T(1), T(2) - временная сложность тела цикла 1-го (верхнего) уровня и 2-го уровня (вложенного цикла) соответственно. В примере T(2) = 2. a(1) - временная сложность операторов, предшествующих вложенному оператору цикла, в теле цикла верхнего уровня. В примере a(1) = 1. b(1) - временная сложность операторов, следующих после вложенного оператора цикла, в теле цикла верхнего уровня. В примере b(1) = 2. T – временная сложность всего алгоритма. a – временная сложность операторов, предшествующих циклу, в основном алгоритме. В примере a=1. b – временная сложность операторов, следующих после цикла в основном алгоритме. В примере b=1. T = a+b+k∙ (a(1) +b(1)) + T(2)∙
11) Под рекурсией понимается метод определения функции через её предыдущие и ранее определенные значения, а так же способ организации вычислений, при котором функция вызывает сама себя с другим аргументом. При прямой рекурсии процедура содержит вызов себя в собственном теле, например:
|