Действие параметра q

Стоит подробнее изучить роль параметра q в классе рекуррентных отношений T(n) < qT(n/2) + O(n), определяемых (5.3). С q = 1 время выполнения получается линейным; с q = 2 оно равно O(n log n); при q > 2 достигается полиномиальная граница с показателем степени больше 1, возрастающим с увеличением q.
При- чина таких различий во времени выполнения связана с тем, на какой стадии выполняется большая часть работы в этой рекурсии: при q = 1 в общем времени выполнения преобладает верхний уровень, тогда как при q > 2 основная работа выполняется подзадачами постоянного размера на нижних уровнях. Рассматривая происходящее с этой точки зрения, мы видим, что рекуррентное отношение для q = 2 в действительности представляет «баланс»: объем работы, выполняемой на каждом уровне, одинаков для всех уровней, и именно этот фактор обеспечивает время выполнения O(n log n).

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Действие параметра q:

  1. § 3.4. Параметры социальной структуры организации
  2. Временные параметры вопроса
  3. ПАРАМЕТР
  4. 45. Структура и социально-психологические параметры малой группы
  5. § 69 Вознаграждение за убыток от действий. – Понятие об убытке и лишении прибытка. – Ответственность за бездействие. – Кто имеет право на вознаграждение. – Ожидаемый вред. – Связь убытка с действием. – Обязательства, возникающие из преступных действий. – Умысел и степень вины. – Личная обида. – Иск об обиде.
  6. Правило выявления «индивидуального действия» на основе установления стабильности действия по отношению к ситуациям.
  7. Правило выявления «индивидуального действия» на основе установления стабильности действия во времени.
  8. 4. Действия и результат действий как объекты гражданских прав (правоотношений)
  9. IV. 1. 3. Сети. Сеть линий - это любая пара однопараметрических линий на поверхности, гладко зависящих от параметра. примерами могут служить параллели и меридианы на поверхности земного шара.
  10. Нередко предлагаемое в вопросе действие респонденты оценивают как обобщенное, типичное, т.е. как действие, которое они обычно совершают.
  11. § 2 Условное обязательство. – Разные виды условий. – Наступление условия и его действие. – Соотношение условий. – Понятие о сроке. – Действие срока.
  12. Психологические действия — действия, направленные на решение психологических задач и осуществляемые психологическими средствами и приемами.
  13. 17. Понятие социального действия. Идеальные типы социальных действий
  14. § 27 Нужно ли для давности явное, незакрытое владение? – Действует ли давность посреди совместного, общего владения? – В каких случаях приостанавливается действие давности? – Переход владения к преемнику
  15. 1. Понятие недействительности сделок Недействительными сделками являются действия субъектов гражданского права, направленные на установление, изменение или прекращение гражданских прав и обязанностей, но не порождающие желаемых сторонами юридических результатов вследствие несоответствия совершенных действий требованиям закона.
  16. § 71 Вознаграждение за вред от действий непреступных. – Мера ответственности. – Ответственность за случайные действия. – Ответственность господ и хозяев, владельцев, родителей и опекунов. – Закон об ответственности железнодорожных управлений. – Особое значение иска об убытках, власть суда и способы доказательства. – Авария или морские убытки.
  17. АКЦЕПТОР ДЕЙСТВИЯ