Поясните, пожалуйста, верно ли, что $%\Theta(2^n)=\Theta(3^n)$% в понимании теории вычислительной сложности? Мне казалось, что нет. Википедия со мной согласна: 5-й пример. Да и вообще, согласно определению $%\Theta$% через пределы функций, получается бесконечность, следовательно функции асимптотически не эквивалентны.

Однако в одной из лекций MIT английским по белому сказано (здесь, стр. 5), что изменение основания степенной функции влияет лишь на мультипликативную константу. Поэтому, касательно $%\Theta$%, если основание не зависит от $%n$%, то оно может быть любым.

Спасибо


Дополнение 1:

$%O$% подразумевает ограничение функции сверху, $%\Theta$% — сверху и снизу. Определения: $%f \in \Theta(g) \Leftrightarrow \exists\ c_1,c_2 > 0\ \exists\ x_0 > 0\ \forall\ x > x_0: c_1\cdot|g(x)|\le|f(x)| \le c_2\cdot|g(x)|$%

Кроме того: $% f \in \Theta(g) \Leftrightarrow 0 < \liminf_{x \to a} \left|\frac{f(x)}{g(x)}\right| \le \limsup_{x \to a} \left|\frac{f(x)}{g(x)}\right|< \infty$%

задан 25 Апр '14 0:40

изменен 25 Апр '14 1:03

10|600 символов нужно символов осталось
1

Вы всё правильно понимаете. На пятой странице, которую Вы указали, написан бред. Несмотря на то, что издание уважаемое: $$1.6^n\neq \Theta(e^n).$$ Изменение основания добавит не мультипликативную константу, а показательную функцию.

PS: при изучении экспоненциальных алгоритмов часто рассматривают: $$g(n) = O^*(f(n)) \Leftrightarrow\exists p(n)\text{ - многочлен}\quad \forall n\geqslant n_0\quad g(n)\leqslant p(n)\cdot f(n).$$

Но даже многочлен не спасёт при изменении основания показательной функции хотя бы на \eps > 0.

ссылка

отвечен 25 Апр '14 2:43

изменен 25 Апр '14 2:54

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×90
×76
×29

задан
25 Апр '14 0:40

показан
815 раз

обновлен
25 Апр '14 2:54

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru