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

解决方案 »

  1. 1、如果n/5是计算机的整除,结果是log5(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
      


  2. 这个就更优化了,估计最坏结果是试验18次T(n)=25T(n/5)+n*n的时间复杂度?这一题没人会么?
      


  3. 第一题要算一下,不是一眼就能看出来,不过我估计答案应该是Lg N/Lg 5什么什么的
      

  4. 第一题应该是O(n)= n*nlog5(n);
      


  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
    这应该是标准的答案了,这题挺经典的,网上的答案挺多的,没想到还会考。
    当然,这题不是我做出来的,也是做不出来网上搜的。
      

  6. ◎ 1、T(n)=25T(n/5)+n*n的时间复杂度?
    我觉得这个可能不是表面上能直接推导的答案,这个题目估计是可深可浅的;
    首先是要强调下精度问题,否则 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顶黑,就知道自己一定黑;那么应该是三顶。
      

  7. j2ee,ssh,oracle...二十余个java内部项目视频,少年,要相信项目改变命运,Q1583539597
      

  8. 这个第2题,选10楼10楼得扔是不是可以认为是这么个原因,假设第一颗从第K层扔(不碎再从2K层上扔),那么最坏的情况下是K-1+100/K,而K+100/K只有取10才能使不等式最小
      


  9. 第二题我又想了下,其实应该就是 B+Tree 算法,在限制了层高的情况下,要求最优化搜索效果。所以 节点数 开 N次方应该是对的。
      

类似问题 »