Как доказать или опровергнуть: 1) 2^(n+1)=O(2^N); 2) 2^2N != O(2^n)?

Question

[tj57]

https://www.daniweb.com/programming/computer-scien... - здесь есть примерные объяснения,но точного решения нет

Answer 1

[jcmvbkbc]

Как доказать или опровергнуть

Воспользоваться определением:
2^(n+1)=O(2^N) означает, что найдётся x0 и M, такие, что для любого x > x0, 2^(x+1) < M * 2^x. Деля обе части на положительное 2^x получаем 2 < M. Т.е. оно справедливо для любого x0 и M > 2.

Answer 2

[Евгений Кучеренко]

Подставьте 1, 2, ... 10 и проверьте)

Если более строго, поделите левую часть на правую, возьмите предел при N -> к бесконечности. Если равенство сохраняется (1 = 1), то верно:

1. Верно, при большом N: (N + 1) / N = 1
2. Верно, при любом N: 2^2N / 2^N = 2^N != 1

Comments

[jcmvbkbc]

> 2^2N / 2^N = 4
ух ты как прикольно вы степени делите.

[Евгений Кучеренко]

jcmvbkbc: пардон, спасибо)

[jcmvbkbc]

> Если равенство сохраняется (1 = 1)
Евгений Кучеренко: ну и в дополнение, O большое не так работает. Грубо говоря, предел должен быть константой, но не обязательно единицей.

[Евгений Кучеренко]

jcmvbkbc: Мы рассматриваем конкретный случай проверки утверждения, поэтому можно смело делить, поэтому правая часть будет == 1

[jcmvbkbc]

Евгений Кучеренко: нельзя утверждать смело, когда в пределе получается 4, хоть и неправильно, а вы говорите, что проблема в том, что 4 != 1. Не в этом проблема. Вот скажите, как математик математику, 4n = O(n) или нет?

[Евгений Кучеренко]

jcmvbkbc: Да, понял о чем вы. Конечно