Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Выражение L(n)=(2+o(1))*f(n) - чуть более точное чем... 23.09.04 22:24 Число просмотров: 4436
Автор: RElf <M> Статус: Member
|
> > Эти формулы выдраны из O-нотации, поэтому верхняя
> оценка
> > здесь выглядит как c*L(n), где c - некоторая
> константа. Без
> > знания константы c эти формулы не имеют смысла для
> > конкретных значений n, поэтому ни о каких "верхних
> оценках"
> > на количество операций речи идти не может.
>
> Сама функция задаётся непосредственно как L(n), а не как
> O(f(n)). Однако L(n) содержит в себе множитель (перед
> произведением логарифмов) (2+o(1)).
Выражение L(n)=(2+o(1))*f(n) - чуть более точное чем L(n)=O(f(n)), но по сути оба эти выражения показываютасимптотикуроста L(n) и ничего больше.
> Доказывается (нам, к
> сожалению, давали без доказательства), что при n=pq, она
> приводится к виду, который я выше показал. И для такого
> частного случая o-нотация тут уже не при чём.
Еще как причем. В выражение, содержащее O() или o(), подставлять конкретные значение n бессмысленно. Так такое выражение задает не количество, а всего лишь оценивает асимптотику. Например, в той же o(1) при конкретном значении n может сидеть величина типа 10^100; само же выражение o(1) означает просто, что эта величина стремится к 0 при n стремящемся к бесконечности, но никакой информации о том как именно она стремится нет.
> А константа "c" зависит уже от оборудования, на котором считать. Как я
> уже писал - она показывает именно количество операций w.
> Если ошибаюсь, поправьте.
Не только от оборудования, от n она вообще говоря тоже зависит (см. выше).
|
|
|
подробно о проекте
Анализ криптографических сетевых...
