Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Это уже Вы что-то путаете.. 29.12.04 17:56 Число просмотров: 3145
Автор: Heller <Heller> Статус: Elderman
|
> > По поводу ассимтотики. Если разобраться, то
> > "сложность=O(x^2)" означает ни что иное, как
> "сложность
> > возрастает при возратании x быстрее чем функция x^2 (в
> Нет. O-нотация говорит о том, что возрастание функции в
> пределе РАВНО возрастанию того, что в скобках у O.
>
> То бишь если говорить что f(x) = O(g(x)), то
> limit(x = infinity, f(x) / g(x)) = 1;
> Неправильно. limit(x = infinity, (x ^ 2) / (x^0.5)) =
> infinity, а не 1. Следовательно говорить об эквивалентности
> O(x^2) и O(x^0.5) не следует
Вообще-то A(x)=O(B(x)) говорит о том, что A(x) имеет более высокий порядок роста, чем B(x), то есть функция A(x)/B(x) должна быть бесконечно большой - это определение. Слово "РАВНО" откуда взялось непонятно (если только нас умышленно обманывают в институте).
Далее, об ЭКВИВАЛЕНТНОСТИ я не сказал ни слова. Зато есть такое очевидное свойство:
A(x)=O(B(x)) && B(x)=O(C(x)) => A(x)=O(C(x))
Это следует из определения. А отсюда:
limit(x = infinity, (x ^ 2) / (x^0.5)) = infinity =>
=> x^2=O(x^0.5)
А эквивалентность - это действительно, когда в пределе получается единица - но я и не говорил, что они эквивалентны. Я говорил что из того, что f=O(x^2) можно утверждать, что f=O(x^0.5) - и это действительно так. Во всяком случае я пока не вижу почему не наоборот. И вот задача не найти чё-нить, что можно поставить после буквы "O", а доказать, что то что там в скобках стоит - это самая быстрорастущая функция, однако имеющая более низкий порядок роста чем f.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
