TCS课堂笔记：数据库存储问题
理论计算机(I)课上讲的一个问题，很有意思。
已经一个n，m和
里n个数，设计一种保存这n个元素的表的数据结构形式，使得对中任何一个数，可以最少的查询次数（每次查询，可以选择一个位置，然后你能知道表中这个位置的数据），获知这个数是否在表中。
如果设计这个表为有序表，用二分法需要
次查询。
有序表是最优的么？
举一个例子，一个保存1，2，3里面的两个数的有序表，要想知道2是否在这个表里面，至少需要两次查询。可不可以用一种特定的数据结构，使得一次查询就能判定任何一个数是不是在数据库里面？
结论是可能的，见下图：
一般的，假如表里的n个数的范围是1，2，...，2n-2，即
，可以设计一种方法，使得，对于任何一个数，只需要查询一次，便能知道这个数是否在这个表里面。
课堂上有同学当场就想出设计方法，向他致敬！
另外，利用广义的Ramsey定理，对于固定的n，能够证明当m足够大时，无论你怎么设计那个表的结构，也至少需要的查询次数。
一个很神奇的问题。相关论文Should Table be Sorted?, 上面的图片也来自这篇文章。
的计算及纪录
一般的，假如表里的n个数的范围是1，2，...，2n-2，即m=2n-2，可以设计一种方法，使得，对于任何一个数，只需要查询一次，便能知道这个数是否在这个表里面。
另外，利用广义的Ramsey定理，能够证明当m足够大时，无论你怎么设计那个表的结构，也至少需要\log n的查询次数。
这两段没看懂，假如当m足够大时，并且m=2n-2，需要多少次查询呢？
这两段不是连着的。后面那个是说当n固定，m足够大时，不会有比有序表更好的方法。
这样行不行?
模n 取同余, 把那些唯一的可以放到表里面去, 有重复的中间, 取出一半找那些空位置放(这个空位置我还没想好怎么找, 应该找那些取模剩余中间不包括的才好) 然后另一半如果放到原位, 就没法标记自己了, 所以可以错排一下放, 这样标记了自己也在里面.
这样, 如果找到自己就是在里面, 如果找到和自己模N 取余一样的, 就表示不在自己里面. 如果遇到同余不一样的, 就看是前一半还是后一半, 前一半表示在里面, 后一半就表示自己不在里面.
不过 2n-2 这些都没想通, 而且前一半后一半怎么区分呢, >n 么... 智商有限了...
我说错了, 取模一样的不可能在自己格子里, 应该是看前一半还是后一般. 还有, 看过Andrew的了, 从证明到算法, 除了佩服没话说.
HI 这是个有趣的问题。
楼主能否给出这种情况的存储设计
从集合{1,2,3,4,5，6}中选4个。