在2004上5月考题:类比二分搜索算法，设计k分搜索（k为大于2的整数）如下：首先检查n/k处（n为被搜索集合的元素个数）的元素是否等于要搜索的值，然后检查2n/k处的元素，…，依次类推，或者找到要搜索的元素，或者把集合缩小到原来的1/k；如果未找到要搜索的元素，则继续在得到的集合上进行k分搜索；如此进行，直至找到要搜索的元素或搜索失败。此k分搜索算法在最坏情况下搜索成功的时间复杂度为__(64)__，在最好情况下搜索失败的时间复杂度为__(65)__。
(64) A. O(logn) B. O(nlogn) C. O(logkn) D. O(nlogkn)
(65) A. O(logn) B. O(nlogn) C. O(logkn) D. O(nlogkn)
若视频图像序列中两帧相邻图像之间存在着极大的相关性，则这种相关性称为__(44)B__冗余。
（44）A.空间 B.时间 C.视觉 D.信息熵
请高手讲解一下这两道题,本人不太懂,越详细越好,谢谢
(64) A. O(logn) B. O(nlogn) C. O(logkn) D. O(nlogkn)
(65) A. O(logn) B. O(nlogn) C. O(logkn) D. O(nlogkn)
若视频图像序列中两帧相邻图像之间存在着极大的相关性，则这种相关性称为__(44)B__冗余。
（44）A.空间 B.时间 C.视觉 D.信息熵
请高手讲解一下这两道题,本人不太懂,越详细越好,谢谢
64A65C猜的
44A不知道正确不？
（44）A.空间 B.时间 C.视觉 D.信息熵 这一题，非常肯定的告诉你，答案是B。
这是概念问题，记得看书了。
设计k分搜索算法（k为大于2的整数）如下：首先检查n/k处（n为被搜索集合的元素个数）的元素是否等于要搜索的值，然后检查2n/k处的元素，…，这样，或者找到要搜索的元素，或者把集合缩小到原来的1/k；如果未找到要搜索的元素，则继续在得到的集合上进行k分搜索；如此进行，直到找到要搜索的元素或搜索失败。此k分搜索算法在最坏情况下搜索成功的时间复杂度为__(64)__，在最好情况下搜索失败的时间复杂度为__(65)__。
答案为 64C. O(logkn) 65C. O(logkn)
按照树的角度理解：
64问的意思是最坏情况下搜索成功的时间,情况最坏也就是说可能是倒序了,这样的情况下要查找成功必然要查找完整棵K叉树了,自然查找的时间就是这棵树的树高logkn了.65问的意思也是要找到整棵树所以也是logkn.
最坏情况下搜索成功，就是将集合缩小到不可再分的程度，同时位于原集合的最后面，那么要搜索成功要进行k次，假设搜索程序的执行频度为f（n），那么
所以T(n)＝O(logkn)
最好情况下搜索失败，那么也一定将集合缩小到不可再分的程度，显然也要进行k次。
一个类同的题目：
用递归算法实现n个相异元素构成的有序序列的二分查找，采用一个递归工作栈时，该栈的最小容量为：
最坏情况下如果要查找的值不在顺序表中，需要的栈容量最大。设经过x分解，即经过x次递归调用后，有low>＝high，2x>=（n＋1），得到x>=log2(n+1).x是整数，需要的最小栈容量即是log2（n＋1）向上取整。