简答题

与顺序查找算法相比,折半查找算法的时间复杂性有多大程度的降低?它是如何提高算法的效率的?

正确答案

顺序查找的时间是O(n),折半查找O(logn)降低了一个数量级。
采用分治策略,每一次比较可以排除一半的数据。

答案解析

相似试题
  • 编程实现二分查找算法。二分(折半)查找(搜索)算法如下:

    简答题查看答案

  • 下面是二分法(折半)查找算法。在给定有序(从小到大)的顺序表中,查找关键字值为k的记录,若找到,返回记录下标,否则返回-1。

    简答题查看答案

  • 常用查找算法有顺序查找、二分查找、分块查找,这三种查找的时间效率由低到高的排列顺序为()

    填空题查看答案

  • 以下函数在a[0]到a[n-1]中,用折半查找算法查找关键字等于k的记录,查找成功返回该记录的下标,失败时返回-1,完成程序中的空格。

    简答题查看答案

  • 以下函数在a[0]到a[n-1]中,用折半查找算法查找关键字等于k的记录,查找成功返回该记录的下标,失败时返回-1,完成程序中的空格。

    简答题查看答案

  • 设计顺序查找算法,将哨兵设在下标高端。

    简答题查看答案

  • 能够在链接存储的有序表上进行折半查找,其时间复杂度与在顺序存储的有序表上相同。

    判断题查看答案

  • 下面函数用“折半查找法”从有10个数的a数组中对关键字m查找,若找到,返回其下标值,否则返回-1,请填(2)空使程序完整。 经典算法提示: 折半查找法的思路是先确定待查元素的范围,将其分成两半,然后比较位于中间点元素的值。如果该待查元素的值大于中间点元素的值,则将范围重新定义为大于中间点元素的范围,反之亦反。

    填空题查看答案

  • 在顺序表中查找某个元素时,需要将当前元素与要找的元素进行若干次的比较,算法经常用while循环来实现,while里面的条件是()且没找到。

    填空题查看答案