RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискрет. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискрет. матем., 1995, том 7, выпуск 3, страницы 8–18 (Mi dm584)  

Некоторые оценки для распределения высоты дерева цифрового поиска

В. А. Ватутин, В. Г. Михайлов


Аннотация: Пусть $\varkappa(T)$ — высота $q$-арного дерева цифрового поиска $T$, построенного по ключам $K_1,\ldots,K_n$, каждый из которых является вектором с компонентами, принадлежащими алфавиту $\mathfrak A=\{0,1,\ldots,q-1\}$. В предположении, что компоненты векторов независимы и равномерно распределены на $\mathfrak A$, найдены оценки сверху и снизу для вероятностей $\boldsymbol{\mathsf P}\{\varkappa(T)\le m\}$, $m=1,\ldots,n$, с явно выписанными константами. Для типичных значений $m$ полученные соотношения являются асимптотически более точными по сравнению с утверждением, доказанным в [2].
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проект 93–011–1443.

Полный текст: PDF файл (966 kB)

Англоязычная версия:
Discrete Mathematics and Applications, 1995, 5:4, 289–300

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.2
Статья поступила: 02.12.1993

Образец цитирования: В. А. Ватутин, В. Г. Михайлов, “Некоторые оценки для распределения высоты дерева цифрового поиска”, Дискрет. матем., 7:3 (1995), 8–18; Discrete Math. Appl., 5:4 (1995), 289–300

Цитирование в формате AMSBIB
\RBibitem{VatMik95}
\by В.~А.~Ватутин, В.~Г.~Михайлов
\paper Некоторые оценки для распределения высоты дерева цифрового поиска
\jour Дискрет. матем.
\yr 1995
\vol 7
\issue 3
\pages 8--18
\mathnet{http://mi.mathnet.ru/dm584}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1361490}
\zmath{https://zbmath.org/?q=an:0849.68023}
\transl
\jour Discrete Math. Appl.
\yr 1995
\vol 5
\issue 4
\pages 289--300


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm584
  • http://mi.mathnet.ru/rus/dm/v7/i3/p8

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретная математика
    Просмотров:
    Эта страница:386
    Полный текст:88
    Первая стр.:3

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019