1、T(n)=25T(n/5)+n*n的时间复杂度？
2、有一幢100层高的大楼，给你两个完全相同的玻璃围棋子。
假设从某一层开始，丢下玻璃棋子就会破碎。那么怎么利用手中的两颗棋子，
用一种什么样的最优策略，知道这个临界的层高呢？
3、一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其它人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什幺帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？笔试部分：
1、定义{1, 2, ... n}*{1, 2, ... n}上的等价关系~
(a, b)~(c, d)当且仅当a+b=c+d。
定义集合A(a, b) = {(x,y)|(x,y)~(a,b)},
那么{1, 2, ... n}*{1, 2, ... n}上不同集合的数量为( )
A、n B、2*n-1 C、2*n D、n*n
2、有一幢100层高的大楼，给你两个完全相同的玻璃围棋子。
假设从某一层开始，丢下玻璃棋子就会破碎。那么怎么利用手中的两颗棋子，
用一种什么样的最优策略，知道这个临界的层高呢？
3、一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其它人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什幺帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？笔试部分：
1、定义{1, 2, ... n}*{1, 2, ... n}上的等价关系~
(a, b)~(c, d)当且仅当a+b=c+d。
定义集合A(a, b) = {(x,y)|(x,y)~(a,b)},
那么{1, 2, ... n}*{1, 2, ... n}上不同集合的数量为( )
A、n B、2*n-1 C、2*n D、n*n
2、同1L
3、同1L。如果只有一顶黑，戴黑帽者首轮就知道耳光。两顶，首轮时候，两顶黑帽者都觉得对方应该耳光，但实际没有，所以次轮时候，耳光响起。递归地，三顶黑帽情况可以从两顶推导：次轮没有耳光，那么黑帽肯定2+，三个黑帽者都只看见两顶，那么说明有一顶在自己头上，所以三轮耳光响起
4、若n->无穷大，A(a,b)元素个数为a+b，所以我觉得这题似乎少了条件……又因为a!=b时(a,b)与(b,a)不同，默认n <= a+b，似乎答案应该是2(n-1)。要选的话我会选B
这个就更优化了，估计最坏结果是试验18次T(n)=25T(n/5)+n*n的时间复杂度？这一题没人会么？
第一题要算一下，不是一眼就能看出来，不过我估计答案应该是Lg N/Lg 5什么什么的
3. 分析 根据主定理，题目中的f(n)=n^2正好第二种情况，结果为T(n)=(n^2) * logn
如果题目稍作修改：T(n)=25T(n/5)+n^3，则为第三种情况，结果为n^3
T(n)=25T(n/5)+n^1.5，则为第一种情况，结果为n^2
这应该是标准的答案了，这题挺经典的，网上的答案挺多的，没想到还会考。
当然，这题不是我做出来的，也是做不出来网上搜的。
我觉得这个可能不是表面上能直接推导的答案，这个题目估计是可深可浅的；
首先是要强调下精度问题，否则 n/5 永远也不会是0，这个计算式可以无穷计算下去；所以要设定一个精度，如果牛B的话，可以直接告诉考官，double的有效位数是xxoo，所以如果计算层级超过多少其实就没有意义了；比如： T(1万) = 25×T(2千) + 1万×1万 = （25×T(4百) + 2千×2千）+ 1万×1万
那么情况很明显：1万×1万 = 1亿；而2千×2千 = 4百万；4百×4百 = 16万；收敛极快，每次约收敛2位数。依稀记得double的有效位数是15位，那么按照这个收敛速度，8次迭代就已经超出double所能表示范围，所以如果按照double的精度来考虑的话，复杂度是一个常量：O(5)◎ 2、有一幢100层高的大楼，给你两个完全相同的玻璃围棋子。假设从某一层开始，丢下玻璃棋子就会破碎。那么怎么利用手中的两颗棋子，用一种什么样的最优策略，知道这个临界的层高呢？这个题目也是个开放式考题，题目里面并没有限制扔的次数，所以完全可以从 1 楼慢慢往上逐层网上扔，这样某层碎了就说明下一层是临界。
但显然这样做求解次数过多，平均来看达到50次；且没有利用2颗的优势，所以可以优化：
第一颗：按照每10层（100层开2次方）去扔一次，碎了后开始第二颗；
第二颗：在碎了的下面10层，逐层扔一次；
优化后平均来看扔10次就可以得到精确解；如果有3颗，就100层开3次方。
当然也许有更好更脑筋急转弯的方式，我就想不到了。
◎ 3、一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其它人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什幺帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？这个题目貌似并非开放式题目，要耐心推导：
第一次开灯后如果只有1顶，那么某人必然看到所有人都是白帽子，就知道自己一定是黑的；所以不止1顶；
第二次开灯时所有人都知道不止1顶，那么只要某人看到所有人只有1顶黑，就知道自己一定是黑；所以不止2顶；
第三次开灯时所有人都知道不止两顶，那么只要某人看到所有人只有2顶黑，就知道自己一定黑；那么应该是三顶。
第二题我又想了下，其实应该就是 B+Tree 算法，在限制了层高的情况下，要求最优化搜索效果。所以 节点数 开 N次方应该是对的。