Dynamic optimality - almost competitive online binary search tree

机译：动态最优-几乎竞争性在线二进制搜索树

获取原文

页面导航

摘要
著录项
相似文献
相关主题

摘要

We present an O(lg lg n)-competitive online binary search tree, improving upon the best previous (trivial) competitive ratio of O(lg n). This is the first major progress on Sleator and Tarjan's dynamic optimality conjecture of 1985 that O(1)-competitive binary search trees exist.

机译：我们呈现O（lg lg n） - 竞争力的在线二进制搜索树，从而改善O（LG N）的最佳先前（琐碎的）竞争比率。这是1985年散流器和Tarjan的动态最优猜测的第一个重大进展，即o（1） - 竞争力二元搜索树。

著录项

来源
《Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on》|2004年|p.484-490|共7页
会议地点
作者
Demaine E.D.; Harmon D.; Iacono J.; Patrascu M.;
展开▼
作者单位

展开▼
会议组织
原文格式 PDF
正文语种
中图分类无线电电子学、电信技术;
关键词
optimisation; computational complexity; trees (mathematics); dynamic optimality; competitive online binary search tree;

机译：优化;计算复杂度;树（数学）;动态最优性;竞争性在线二进制搜索树;

相似文献

外文文献
中文文献
专利

1. Statically Optimal Binary Search Tree Computation Using Non-Serial Polyadic Dynamic Programming on GPU's [J] . Mohsin Altaf Wani, Manzoor Ahmad International journal of grid and high performance computing . 2019,第1期

机译：在GPU上使用非串行多态动态编程的静态最优二叉搜索树计算
2. An Efficient CGM-Based Parallel Algorithm for Solving the Optimal Binary Search Tree Problem Through One-to-All Shortest Paths in a Dynamic Graph [J] . Vianney Kengne Tchendji, Jerry Lacmou Zeutouo Data Science and Engineering . 2019,第2期

机译：一种有效的基于CGM的并行算法，用于通过动态图中的一条至全部最短路径来求解最佳二叉搜索树问题
3. Efficient construction of Optimal Binary Search Trees using Data Preprocessing to improve Quality and Attribute Post computing to save Space and time through modified Dynamic Programming Technique [J] . S.Hrushikesava Raju, Dr. T.Swarna Latha International Journal on Computer Science and Engineering . 2016,第1期

机译：通过改进的动态规划技术，使用数据预处理有效构建最佳二叉搜索树，以提高质量和属性后计算，从而节省空间和时间
4. Dynamic optimality - almost competitive online binary search tree [C] . Demaine E.D., Harmon D., Iacono J., IEEE International Workshop on Current and Defect Based Testing . 2004

机译：动态最优 - 几乎竞争在线二进制搜索树
5. Data structures, binary search trees: A study of random Weyl trees [D] . Goudjil, Amar 1999

机译：数据结构，二叉搜索树：随机Weyl树的研究
6. A Fast Framework for Abrupt Change Detection Based on Binary Search Trees and Kolmogorov Statistic [O] . Jin-Peng Qi, Jie Qi, Qing Zhang 2016

机译：基于二叉搜索树和Kolmogorov统计量的突变检测快速框架
7. An O(loglog n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times [O] . Bose, Prosenjit, Douïeb, Karim, Dujmovic, Vida, 2010

机译：具有最优最坏情况的O（loglog n） - 竞争二元搜索树访问时间

Dynamic optimality - almost competitive online binary search tree

摘要

著录项

相似文献

相关主题

期刊订阅