|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Pavel Arapov 2:5015/113.34 04 Jan 2002 19:35:25
To : Yurij Zabelyshynskij
Subject : Re: O() o()
--------------------------------------------------------------------------------
и я решил ответить....
>> А вот трактование O() по Кнуту.
>> Запись O(f(n)) всегда обозначает следующее: существует
>> положительные константы M и n0? такие, что величина xn,
>> представленная в виде O(f(n)), удовлетворяет условию
>> |xn|<=M|f(n)| для всех целых n>=n0.
>> Формулы содержащие запись O(f(n)), можно рассматривать
>> как множества функций от n. Запись O(f(n)) обозначает
>> множество всех функций g от целых чисел, для которых
>> существуют константы M и n0, такие, что |g(n)|<=M|f(n)|
>> для всех целых n>=n0.
YZ> Сначала я не поверил, что Кнут мог написать такую чушь, но ... :( В
YZ> общем, будем считать, что он погорячился, говоря здесь о множествах.
YZ> Во-первых, если это множество, то надо писать
YZ> f(n) \принадлежит O(g(n))
Так как мы не знаем что за f(n), то можем трактовать, что это множество
функций.
YZ> Во-вторых, как тогда трактовать запись
YZ> n = O(n^2) ?
^^^^^^^^^^
Запись не понятна, так как мы приравниваем n к функции от n, то тут где-то
ошибка. Мы можем писать так, например:
f(n)=O(g(n)) и пример на запись Hn=ln(n)+y+O(1/n), трактуется как "n-ое
гармоническое число равно натуральному логарифму n плюс константа Эйлера плюс
некоторая велечина, которая составляет О большое от 1 на n - эта величина не
определена точно, однако, мы можем утверждать, что она не превосходит константу
умноженную на 1/n."
YZ> Слева ведь стоит конкретная фунция, а вовсе не множество функций.
YZ> В-третьих, как тогда понимать "величина xn, представленная в виде
YZ> O(f(n))"?
про понятия. Величина xn-это последовательность, где n-порядковый номер, то
есть получаем результат от натурального n, но так как результат мы не можем
получить точный то представляем его в виде O(f(n)), то есть каково не было бы n
мы можем утверждать, что оно не превосходит f(n) умноженное на некоторую
константу.
;)
*С наилучшими, Yurij* .
--- Fips 2000 ---- cool 'nino' edition
* Origin: Кому я должен, всем прощаю. (2:5015/113.34)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
<без заголовка> |
Ilia Kantor |
26 Dec 2001 23:30:28 |
 Re: |
Sergey Semenov |
02 Jan 2002 19:52:52 |
 Re^2: |
Sergey Politov |
03 Jan 2002 07:38:31 |
 Re: O() o() |
Yurij Zabelyshynskij |
03 Jan 2002 18:18:08 |
 Re: O() o() |
Pavel Arapov |
03 Jan 2002 20:30:05 |
 O() o() |
Ilia Kantor |
03 Jan 2002 22:52:02 |
  Re: O() o() |
Yurij Zabelyshynskij |
04 Jan 2002 00:17:46 |
|
Re: O() o() |
Yurij Zabelyshynskij |
04 Jan 2002 01:20:57 |
 Re: O() o() |
Pavel Arapov |
04 Jan 2002 19:35:25 |
|
Re: O() o() |
Yurij Zabelyshynskij |
04 Jan 2002 21:35:22 |
|
Re: O() o() |
Pavel Arapov |
04 Jan 2002 22:52:51 |
|
Re: O() o() |
Andrey Tarasevich |
07 Jan 2002 23:53:29 |
|
Re: O() o() |
Yurij Zabelyshynskij |
08 Jan 2002 00:28:12 |
|
Re: O() o() |
Andrey Tarasevich |
08 Jan 2002 01:49:55 |
|
Re: O() o() |
Yurij Zabelyshynskij |
08 Jan 2002 02:46:56 |
|
Re^2: O() o() |
Sergey Politov |
04 Jan 2002 07:46:40 |
|
Re: O() o() |
Yurij Zabelyshynskij |
04 Jan 2002 18:13:00 |
|
Re^2: O() o() |
Sergey Politov |
05 Jan 2002 07:25:04 |
|
Re: O() o() |
Yurij Zabelyshynskij |
05 Jan 2002 18:26:23 |
|
Re^2: O() o() |
Pavel Arapov |
04 Jan 2002 22:00:51 |
|
Re^3: O() o() |
Sergey Politov |
05 Jan 2002 06:41:33 |
|
Re: O() o() |
Pavel Arapov |
05 Jan 2002 13:01:27 |
|
Re^3: |
Sergey Semenov |
04 Jan 2002 00:43:56 |
|
Re: |
Andrew Ezhguroff |
03 Jan 2002 15:26:12 |
|
Re^2: |
Sergey Semenov |
04 Jan 2002 00:51:34 |
|
Re: O() o() |
Yurij Zabelyshynskij |
03 Jan 2002 17:57:38 |
|
Re^2: O() o() |
Sergey Semenov |
04 Jan 2002 01:12:16 |
|
Re: O() o() |
Yurij Zabelyshynskij |
04 Jan 2002 18:04:49 |
|
Re^2: O() o() |
Sergey Semenov |
09 Jan 2002 00:43:02 |
|
Re: |
Michael Ryazanov |
04 Jan 2002 22:10:00 |
|
<без заголовка> |
Valentin Ermolaev |
04 Jan 2002 20:07:12 |
|
|
