Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Выражение L(n)=(2+o(1))*f(n) - чуть более точное чем... 23.09.04 22:24 Число просмотров: 4121
Автор: 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 она вообще говоря тоже зависит (см. выше).
|
|
|