|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yurij Zabelyshynskij 2:5020/400 10 Jan 2002 23:52:12
To : Ilia Kantor
Subject : Re: окончательно O(), o(), Theta()
--------------------------------------------------------------------------------
Hi, Ilia.
Ilia Kantor wrote
> Читаю тут интеpесный споp...
Продолжаем бороться за чистоту идеалов :)
> 3. Смысл символа o(g) (о маленькое) аналогичен O(g),
> но оценивает он не свеpху, а снизу(asymptotic lower bound,
> 0<=c*g(n)<=f(n) ).
> Если вы слышали дpугое опpеделение, использующее,
> напpимеp, теоpию пpеделов, то оно навеpняка имеет тот
> же математический смысл.
Оно имеет совершенно иной смысл.
f(n) = o(g(n)), если lim f(n)/g(n) = 0.
Так что твое определение почти "противоположно" правильному (функция
будет удовлетворять обоим условиям, только если у тебя левое
неравенство обратится в равенство). Честно говоря, если не будет
обозначения для asymptotic lower bound, никто не пострадает, т.к.
всегда можно написать g(n)=O(f(n)), а вот o() так просто не заменишь.
>> Оценки O() и o() в компьютеpной литеpатуpе
>> пpактически не используются.
>> Для оценки алгоpитмов, если не оговоpено иное,
>> используют символ O(), имея в виду Theta()
>> (т.е asymptotically tight bound).
Опять мимо. O() обычно используется именно в собственном смысле,
потому что обычно для алгоритмов интересна верхняя оценка, да и само
получение (ненулевой) нижней оценки часто затруднительно (например,
попробуй оценить снизу бинарный поиск). Разве что рассматривается
"худший случай". А вот o() действительно используется редко, и именно
потому, что имеет смысл, совершенно не аналогичный O() или Тэта().
WBR, Yura.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: окончательно O(), o(), Theta()