二分查找的算法时间复杂度

Question

我想弄清楚我的算法的时间复杂度是多少，我知道我有带二分查找的算法，一般来说是 O(log n)。但是我在两个常量之间搜索，即 x=1 和 x = 2^31 - 1（整数的大小）。我认为在最坏的情况下我的时间复杂度是 log2(2^31) = 31，所以二分查找在最坏的情况下需要 31 个步骤。但是，我在二分搜索中的每一步都调用了一个函数，该函数具有 O(n) 运行时间（只有输入大小的一个循环）。我的算法会是简单的 O(31n)=O(n) 阶吗？

我的算法的输入：一个键，两个大小为n的数组a和b。

在代码中它看起来像这样：

    binarySearch(key, a, b)
    min = 0, max = 2^31 - 1
    mid = (min + max) / 2
    while (min<=max) { 
        x = function(mid, a, b); //this function has O(n)
        if (x==key) {
            return mid;
        } else if (x < key) { 
            min = mid + 1
        } else {
            max = mid - 1
        }
        mid = (min + max) / 2
    }
    return KEY_NOT_FOUND

我只是想确定一下，如果你的时间复杂度（减少的）来了，请解释你的答案。

Answer 1

更新

是的，你完全正确。

在最坏的情况下 function() 将被调用 31 次，每次调用需要时间 O(n)，因此算法的运行时间简单地由 [=13= 给出].

原题的解x = function(mid)

你的问题有点可疑，你算法的时间复杂度应该是O(1).

当我们谈论算法的时间复杂度时，有一点很重要：

We always consider the time that the algorithm requires with respect to the size of it's input.

在以下代码段中：

x = function(mid); //this function has O(n)

虽然 function() 可能是线性时间函数，但在您的情况下，function() 仅从集合 {0, 1 , ..., 2<sup>30</sup>}, 所以在最坏的情况下 function() 计算时间 max{T(0), T (1), ..., T(2<sup>30</sup>)} = T, 是常数!

所以在最坏的情况下，你的 while 循环将调用 function() 31 次，所以在最坏的情况下你的算法运行时间 31 * T，这是一个常数。

注意你算法的输入是key，你算法的最坏情况运行时间是31 * T，其实是独立您输入的大小 key！所以时间复杂度是O(1).

对于你的情况，我认为用大 O 表示法来讨论时间复杂度是不合适的。我建议你谈谈最坏情况下所需的计算步骤数。

二分查找的算法时间复杂度

Algorithm time complexity with binary search

time

big-o

binary-search

time-complexity

binary-search-tree