|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yurij Zabelyshynskij 2:5020/400 08 Jan 2002 00:28:12
To : Andrey Tarasevich
Subject : Re: O() o()
--------------------------------------------------------------------------------
Hi, Andrey.
Andrey Tarasevich wrote
> Кормен et al. в "Introduction to Algorithms" определяют
> O, o, омегу, тэту и т.д. как _множества_ функций.
Что-то я такого в Кормене не видел. Hаоборот, несколько раз
встречается фраза о том, например, что O(1) - это ограниченная
функция. Может, мы говорим о разных книгах или разных переводах или
изданиях, я имею в виду Кормен, Лейзерсон, Ривест: "Алгоритмы:
построение и анализ", М.: МЦHМО, 2001 (перевод "Introduction to
Algorithms").
>> Во-первых, если это множество, то надо писать
>> f(n) \принадлежит O(g(n))
> "Introduction to Algorithms": "Такое вольное использование знака
> равенства для обозначения принадлежности множеству может
> на первый взгляд казаться запутывающим, но, как мы увидим
> позже в этой главе, оно имеет свои преимущества"
Вот-вот, ВОЛЬHОЕ использование, даже слишком.
>> Во-вторых, как тогда трактовать запись
>> n = O(n^2) ?
> "Introduction to Algorithms": "Многие читатели, ранее встречавшиеся
> с O-нотацией, могут счесть странным, что мы пишем n = O(n^2).
> Дело в том, что в литературе O-нотация иногда неформально
> используется для описания asymptotically tight bounds, т.е. того,
> что мы определили как тэта-нотацию."
Я имел в виду другое. Сейчас уже неважно, потому что флейм уже
закончен (кажется). Если очень хочешь узнатьть, почему множества здесь
не катят, то можем продолжить в RU.MATH.
WBR, Yura.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
<без заголовка> |
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 |
|
|
