10
TCS 课堂笔记：数据库存储问题
source link: https://zhiqiang.org/cs/tcs-classroom-notes-database-storage-problems.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
TCS 课堂笔记：数据库存储问题
理论计算机(I)课上讲的一个问题，很有意思。
已经一个 n ， m 和{1,2,⋯,m} 里 n 个数，设计一种保存这 n 个元素的表的数据结构形式，使得对{1,2,⋯,m} 中任何一个数，可以最少的查询次数（每次查询，可以选择一个位置，然后你能知道表中这个位置的数据），获知这个数是否在表中。
如果设计这个表为有序表，用二分法需要logn 次查询。
有序表是最优的么？
举一个例子，一个保存 1 ， 2 ， 3 里面的两个数的有序表，要想知道 2 是否在这个表里面，至少需要两次查询。可不可以用一种特定的数据结构，使得一次查询就能判定任何一个数是不是在数据库里面？
结论是可能的，见下图：
一般的，假如表里的 n 个数的范围是 1 ， 2 ，...， 2n-2 ，即m=2n−2 ，可以设计一种方法，使得，对于任何一个数，只需要查询一次，便能知道这个数是否在这个表里面。
课堂上有同学当场就想出设计方法，向他致敬！
另外，利用广义的 Ramsey 定理，对于固定的 n ，能够证明当 m 足够大时，无论你怎么设计那个表的结构，也至少需要logn 的查询次数。
一个很神奇的问题。相关论文Should Table be Sorted?, 上面的图片也来自这篇文章。
Q. E. D.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK