这样的面试题，你会吗？（有奖）

cjaizss

回复  cjaizss


    对角线么？有用么？还是贴代码吧.
hbmhalley 发表于 2011-12-06 11:39

   
    需要代码吗?
xxxxxxxxxxxxxxx
xxxxxxxxxxxxxxx
xxxxxxxxxxxxxxx
xxxxxxx?oooooo
xxxxxxxooooooo
xxxxxxxooooooo
xxxxxxxooooooo
xxxxxxxooooooo
xxxxxxxooooooo
如果?位置的小于所查值,则所查值落在X的区域
如果大于,则落在o的位置
根据这个就可以设计出一个对数级别算法

hbmhalley

回复 50# cjaizss


    最坏情况：f(n) = 3*f(n/2) + 1
    复杂度为 n^1.6

hbmhalley

回复 50# cjaizss


    而且有错误啊
    AC
    BD
    你的意思是B<C么？

cjaizss

回复  cjaizss


    最坏情况：f(n) = 3*f(n/2) + 1
    复杂度为 n^1.6
hbmhalley 发表于 2011-12-06 12:29

    平均满足对数级别.
    最坏情况下的式子也不是你这样,并且结论也不是,你的这个式子级别是不到线性级别的.
   f(n)=f(n/2)+f(n/4)+1
    应为对数平方级别高一些

   以上这一段我算错了,大家不用看了

hbmhalley

回复 53# cjaizss


    主定理证明过的
    不然再贴份代码 这是我验证过的：

1. 
   
2. 
   
3. #include <stdio.h>
   
4. #include <math.h>
   
5. 
   
6. int main () {
   
7.         int k , i;
   
8.         scanf ("%d" , &k) ;
   
9.         double ans = 1 ;
   
10.         for (i = 2 ; i <= k ; ++i) ans = 3*ans+1 ;
    
11.         printf ("%.lf\n" , pow(2,k)) ;
    
12.         printf ("%.lf\n" , ans*2) ;
    
13.         printf ("%.lf\n" , pow (2 , log(3)/log(2)*k)) ;
    
14. }
    
15. 
    

复制代码

平均情况能这么算么？这不是最终的复杂度，怎么能忽略常数呢？
n/4是什么？这里n是矩阵"面积"么？如果这么看，你切掉一个角的矩形和原问题是一个问题么？
还有，我仍然怀疑这个算法，比如：
1 2 3
4 5 6
7 8 9
我要找7
你返回什么?

cjaizss

回复  cjaizss


    主定理证明过的
    不然再贴份代码 这是我验证过的：平均情况能这么算么？这不是 ...
hbmhalley 发表于 2011-12-06 12:55

这个时间复杂度我要仔细想想
    ABCD
    EFGH
    I J KL
    MNOP
当我第一次查找到属于
ABCD
EFGH
IJ
MN
那么我查ABEF 中间那个,就可以区分是
QBCD
E
I
M
还是
FGH
J
N
了

cjaizss

这个时间复杂度我要仔细想想
    ABCD
    EFGH
    I J KL
    MNOP
当我第一次查找到属于
ABCD ...
cjaizss 发表于 2011-12-06 13:01

    也就是,每查一次,搜索区域最少减少1/4, 那么不只平均是对数级别,而是平均/最差都是对数级别

hbmhalley

回复 55# cjaizss


    解释下

    1 2 3
    4 5 6
    7 8 9

    Query : 7

    这组数据吧. 首先找5

hbmhalley

回复 56# cjaizss


    这就是我所说的“二分不干净”的问题所在
    二分是对数级别的，关键在于 f(n) = 1*f(n/2) + 1
    之所以这个系数是1，是因为可以利索地去掉一半
   
    而现在是个矩阵
    如果真的能说明可以干净地去掉几分之几，那么这个算法就是log的
    也就是找到一个方法，能让
        f(n) = a*f(n/b) + 1
    这个式子中 无论b多么接近1，只要a严格等于1就可以

    但是能找到么？您这个算法真的正确么？

cjaizss

回复  cjaizss


    解释下

    1 2 3
    4 5 6
    7 8 9

    Query : 7

    这组数据吧 ...
hbmhalley 发表于 2011-12-06 13:04

哦,我想错了
无论比较结果是大还是小都是三块的
的确不是对数
面积的缩小比例可能越来越接近0