#time-complexity
Вопрос:
.0 < c
Базовый уровень: если(n
Я должен найти Большую Тета-функцию этой рекурсивной функции. Я пытался разработать рекурсивное уравнение, но оно усложняется от уровня к уровню, и никакого образования не видно.
Я также попробовал это — предположим, что c<(1-c). так что — 2T(cn) 1 <= T(cn) T ((1-c)n) 1
Это дало мне некоторую нижнюю границу и верхнюю границу, но не тета-границу 🙁
Комментарии:
1. Вместо того, чтобы публиковать это в виде изображения, пожалуйста, отредактируйте свой вопрос, чтобы включить его непосредственно в текст.
Ответ №1:
Когда c приближается либо к 0, либо к 1, рекурсия приближается к T(n) = T(n-1) 2 (при условии, что T(0) также = 1). Это имеет в качестве решения линейную функцию T(n) = 2n — 1 при n > 0.
Для c = 1/2 рекурсия становится T(n) = 2T(n/2) 1. Похоже, что T(n) = 2n — 1 является решением этой проблемы для n > 0.
Это кажется убедительным доказательством того, что функция T(n) = 2n — 1 является решением для всех c: она работает как на концах, так и в середине. Если мы войдем…
2n - 1 = 2cn - 1 2(1-c)n - 1 1
= 2cn - 1 2n - 2cn - 1 1
= 2n - 1
Мы находим, что T(n) = 2n — 1 является решением для общего случая.
Комментарии:
1. Что ж, это классное решение. Можете ли вы объяснить немного подробнее, почему при приближении c к 0 или 1 рекурсия приближается к T(n-1) 2 ? когда c приближается к 1, например, cn —> n, вы говорите, что его n-1, потому что функция имеет дело только с целыми положительными числами? таким образом, он округляется до n-1.
2. По мере приближения c к 1 cn приближается к n, но из-за округления целых чисел всегда будет на единицу меньше n. Аналогично, 1 — c приближается к нулю, поэтому произведение этого с конечным n также приближается к нулю. @mcr0yal