Экономный алгоритм нахождения средних минимальных расстояний
Аннотация
Пусть заданы n + 1 строк £0 ... , £n с символами из некоторого конечного алфавита. В работе предлагается алгоритм нахождения величин среднего значения fc-го минимального расстояния между строками £о,... , £s для всех значений s <= n. Трудоемкость алгоритма равна O(nm), где m - длина строк.
Список литературы
1. Майоров, В.В. Статистическая оценка обобщенных размерностей /В.В.Майоров, Е.А.Тимофеев //Мат. заметки. - 2002. -Т.71. №5. - C. 697 - 712.
2. Kaltchenko, A., Entropy Estimators with Almost Sure Convergence and an O(n-1) Variance /A.Kaltchenko, En-hui Yang, N.Timofeeva //Information Theory Workshop. 2007. ITW '07. IEEE 2-6 Sept. 2007. - P. 644 - 649.
Для цитирования:
Тимофеева . . Экономный алгоритм нахождения средних минимальных расстояний. Моделирование и анализ информационных систем. 2007;14(3):50-52.
For citation:
Timofeeva N.E. Fast algorithm for finding mean minimum distances. Modeling and Analysis of Information Systems. 2007;14(3):50-52. (In Russ.)
Просмотров: 175
Послать статью по эл. почте 