二进制搜索的算法时间复杂度-Java 学习之路

我想弄清楚算法的时间复杂度是什么，我有二进制搜索算法，一般是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

我只想确定，如果你有时间复杂性（减少的），请解释你的答案 .

1 回答

2
Update

是的，你是对的 .

在最坏的情况下， function() 将被调用31次，并且每次调用都需要时间 O(n) ，因此算法的运行时间仅由 31 * O(n) = O(n) 给出 .

Solution for the original question where x = function(mid)

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

当我们谈论算法的时间复杂性时，一个重点是：

我们总是考虑算法所需的时间与其输入的大小有关 .

在以下代码段中：
```
x = function(mid); //this function has O(n)
```
虽然 function() 可能是线性时间函数，但在您的情况下， function() 仅从集合 {0, 1, ..., 230} 获取输入（ mid ），因此在最坏的情况下 function() 计算时间 max{T(0), T(1), ..., T(230)} = T ，这是一个常数！

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

请注意，算法的输入是 key ，算法的最差运行时间是 31 * T ，实际上是输入大小的 independent key ！所以时间复杂度是 O(1) .

在你的情况下，我不认为谈论大O符号的时间复杂性是合适的 . 我建议你谈谈最坏情况下所需的计算步骤数 .
回复于 2024-04-27T19:46:18+08:00

二进制搜索的算法时间复杂度

1 回答

相关问题