TCS课堂笔记:数据库存储问题

作者:, 发表于

理论计算机笔记

查看该系列所有文章

理论计算机(I)课上讲的一个问题,很有意思。

已经一个n,m和 \(\{1,2,\cdots, m\}\) 里n个数,设计一种保存这n个元素的表的数据结构形式,使得对 \(\{1,2,\cdots, m\}\) 中任何一个数,可以最少的查询次数(每次查询,可以选择一个位置,然后你能知道表中这个位置的数据),获知这个数是否在表中。

如果设计这个表为有序表,用二分法需要 \(\log n\) 次查询。

有序表是最优的么?

举一个例子,一个保存1,2,3里面的两个数的有序表,要想知道2是否在这个表里面,至少需要两次查询。可不可以用一种特定的数据结构,使得一次查询就能判定任何一个数是不是在数据库里面?

结论是可能的,见下图:

sorted table

一般的,假如表里的n个数的范围是1,2,...,2n-2,即 \(m=2n-2\) ,可以设计一种方法,使得,对于任何一个数,只需要查询一次,便能知道这个数是否在这个表里面。

课堂上有同学当场就想出设计方法,向他致敬!

另外,利用广义的Ramsey定理,对于固定的n,能够证明当m足够大时,无论你怎么设计那个表的结构,也至少需要 \(\log n\) 的查询次数。

一个很神奇的问题。相关论文Should Table be Sorted?, 上面的图片也来自这篇文章。

[tags]数据库,理论计算机[/tags]

Q.E.D.


上一篇:"完美"的洗牌次数 - 7次2006年12月15日
在大家玩牌的时候,每一局之前都需要重新洗牌——一次洗牌指将牌分为左右两垛然后穿插放牌,但多少次洗牌才是正当的呢?就我多次打牌的观察,

下一篇:征集3个人分蛋糕的方法2007年9月25日
Yao在课程《理论计算机II》的第一节课上提到的一个问题: 三个人如何平分一块蛋糕? 要求每个人拿到不少于1/3的蛋糕——这里指的是每个人认为自


  • 支持使用微薄、微信和QQ的账户登陆进行评论。由各自网站直接认证,不会泄露你的密码。
  • 登陆后可选择分享评论到所绑定的社交网络,如微薄、人人和QQ空间。
  • 评论提交后无法修改。如需修改,请删除原评论再重新提交。
  • 评论支持LaTeX代码,行内公式请用\(a+b=c\),行间公式请用\[a+b=c\]。公式只支持英文字符。