在王道论坛上看到13级中科大CS复试的面试题,有道友说到面试官问了这样的问题: 1.二分查找(单链表)复杂度 2.写出二分查找用链表实现的时间复杂度递推公式 3.二叉查找的时间复杂度 4.二分法用链表和顺序表哪个更好,为什么?查中间那个节点时间复杂度是多少? 先不说以上问题的答案如何,如果是我遇到的话,我想我只能回答第3个问题。原因如下: 1.二分查找又称折半查找,而折半查找能使用的情况必须同时满足两个条件:a.待排记录序列必须按关键字有序 b.必须采用顺序存储结构 因此二分查找根本不能用链式存储结构,换句话说,二分查找不能用线性链表来实现,而只能用顺序表来实现。另外我们通常称描述二分查找过程的二叉树为二叉判定树(注意与下文的二叉查找树区别)。至于二分查找的时间复杂度,我想大家都知道,就不说了。 2.二叉查找是从二叉查找树(又称二叉排序树)而来,通常二叉查找树采用的是二叉链表的存储结构。二叉查找的时间复杂度(也就是上面的第3个问题),不能笼统地说是O(logN),因为二叉查找树的平均查找长度与树的形态有关。分三种情况:a.最坏的情况,即先后插入的关键字有序时,构成的二叉查找树蜕变为单枝树(除了最后一个叶结点之外,每个结点有且只有一个子结点),其平均查找长度为(n+1)/2,此时的时间复杂度就是O(N)。 b.最好的情况,即二叉查找树的形态和二分查找的二叉判定树相同,其平均查找长度和logN成正比,此时的时间复杂度当然是O(logN)。 c.在随机的情况下,二叉查找树的平均查找长度和是logN等数量级的,此时的时间复杂度可视为O(logN)。 3.二分查找和二叉查找的关系是:二叉查找既拥有类似于二分查找的特性,又采用了链表作为存储结构。 综上,以上题目本身及题目答案已不是重点,希望面试官提的问题严谨些。 |
[在校|研一·研二·研三] 二分查找PK二叉查找
最后一支恋歌
· 发布于 2013-04-12 20:59
· 930 次阅读
转载文章时务必注明原作者及原始链接,并注明「发表于 软院网 RuanYuan.Net 」,并不得对作品进行修改。
楼主相关话题