首页 文章

二进制搜索的时间复杂度更差

提问于
浏览
0

众所周知,对于大小为n的排序数组,二进制搜索在最坏的情况下花费t个时间单位 . 如果输入大小为n / 2,算法在最坏的情况下需要多长时间?

1 回答

  • 0

    我们的新输入与原始输入的差异为2倍 . 因为已知二进制搜索的最坏情况时间具有对数复杂度,所以时间的渐近上限应该相同 . 对于任何原始值为2的倍数的输入,这应该适用 .

相关问题