Для выбора в худшем случае линейной временной неоднозначностью при рассмотрении $ n $, для которых $ t (n)= o (1) $ и $ t (n) \ leq cn $

Question

Я проходил через текстовое введение в алгоритмы Cormen et. al. Там, где я наткнулся на соотношение рецидивов для анализа временной сложности алгоритма линейного выбора, и я чувствовал, что несколько вещей, вероятно, несоответствуют относительно диапазона $ n $ , Размер ввода, для которого $ t (n) $ предполагает, что $ O (1) $ и <класс Span= «Математический контейнер»> $ CN $ в способе замены.

Детали текста следующие:

---

Теперь мы можем разработать рецидивовое повторение для худшего времени работы $ T (N) $ Выбор алгоритма. Шаги 1, 2 и 4 Возьмите $ O (n) $ время. (Шаг 2 состоит из $ O (n) $ Вызывы вставки Сортировать на наборы размера $ O (1) $ < / span> Шаг 3 Требуется время $ t (\ lceil n / 5 \ RCEIL) $ и шаг 5 требует времени максимально время $ T (7n / 10 + 6) $ , предполагая, что t монотонно увеличивается. мы делаем предположение, что кажется немотивированным при первом случае, что любой вход меньше, чем Элементы $ 140 $ Elements требуют $ O (1) $ Time; происхождение магической константы $ 140 $ будет ясно в ближайшее время. $ ^ \ janger $ Поэтому мы можем получить рецидивов

$$ t (n) \ leq \ begin {face} O (1) & \ Quad \ text {Если $ n <140 $ ^ \ dddagger $} \\ T (\ lceil n / 5 \ RCEIL) + T (7n / 10 + 6) + O (n) & \ Quad \ Text {Если $ n \ geq 140 $ ^ \ | $} \\ \ end {Cass} $$

Мы показываем, что время работы является линейным путем замены. Более конкретно, мы покажем, что $ t (n) \ leq cn $ для некоторых соответствующих больших постоянных $ C $ AND Все $ n> 0 $ . Начнем с предположения, предположив, что $ t (n) \ leq cn $ для некоторых соответствующих больших постоянных $ C $ и все $ n <140 $ $ ^ {\ кинжал \ Кинжал} $ ; Это предположение удерживает, если $ C $ достаточно большой. Мы также выбираем постоянную такую, что функция, описываемая $ O (n) $ срок выше (которая описывает нерекурсивный компонент времени работы алгоритма. ) ограничен выше для всех $ n> 0 $ . Подставляя эту индуктивную гипотезу в правую сторону рецидива

$$ t (n) \ leq c \ lceil n / 5 \ RCEIL + C (7n / 10 + 6) + $$

$$ \ leq cn / 5 + c + 7cn / 10 + 6c + $$

$$= 9Cn / 10 + 7c + $$

$$= cn + (- cn / 10 + 7c + an). $$

Что на большинстве $ CN $ Если

$$ - CN / 10 + 7C + A \ leq 0. \ Tag 1 $$

$$ \ iff c \ geq 10a (n / (n-70)) \ Quad \ text {Когда n> 70} $$

Потому что мы предполагаем, что $ n \ Geq 140 $ $ ^ {\ dddagger \ ddagger} $ У нас есть $ n / (n-70) \ leq 2 $ и поэтому выбирая $ c \ geq 20a $ удовлетворит неравенство $ (1) $

---

$$ \ dagger \ Quad \ Text {Заявление здесь соответствует $ \ dddagger $ в отношении рецидива} $$

$$ \ dagger \ dagger \ Quad \ text {Заявление здесь не соответствует $ \ | $ в отношении рецидива} $$

$$ \ dddagger \ dddagger \ Quad \ text {Заявление здесь выполняет соблюдение $ \ | $ в отношении рецидива} $$

---

Я не мог совсем понять это несоответствие, однако я не включал весь алгоритм (доступен в разделе CLRS $ 9,3 $ ), но если это необходимо, пожалуйста, скажите тогда Я буду включать это тоже.

Answer 1

Похоже, что $ \ dagger \ janger $ соответствует $ \ | $ .Вам просто нужно выбрать постоянный $ C $ , который больше или равен постоянной $ \ Gamma $ Скрыто в $ O (1) $ Обозначение в определении $ t (n) $ для $ N <140 $ (т. Е. Линия, помеченная $ \ dddagger $ ).

Тогда, для любого $ n \ in \ {1, \ dots, 139 \} $ , у вас есть $T (n) \ le \ gamma \ le c \ le cn $ , по желанию.