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

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

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.
Статья поступила: 02.12.1993
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.2
Образец цитирования: В. А. Ватутин, В. Г. Михайлов, “Некоторые оценки для распределения высоты дерева цифрового поиска”, Дискрет. матем., 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://mathscinet.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
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/dm584
  • https://www.mathnet.ru/rus/dm/v7/i3/p8
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретная математика
    Статистика просмотров:
    Страница аннотации:541
    PDF полного текста:132
    Первая страница:3
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024