这是对数时间复杂度的例子吗？

Question

人们常说，具有对数时间复杂度的算法 O(log n) 是一种将输入加倍并不一定会使所需工作量加倍的算法。通常，搜索算法是作为具有对数复杂度的算法的示例给出的。

考虑到这一点，假设我有一个函数，它接受一个字符串数组作为第一个参数，以及一个单独的字符串作为第二个参数，returns 中字符串的索引数组：

function getArrayItemIndex(array, str) {
  let i = 0
  for(let item of array) {
    if(item === str) {
      return i
    }
    i++
  }
}

假设这个函数调用如下：

getArrayItemIndex(['John', 'Jack', 'James', 'Jason'], 'Jack')

在这种情况下，该函数将不会在 returns 1 的索引之前逐步遍历整个数组。类似地，如果我们将数组中的项目加倍，这样它最终被调用如下：

getArrayItemIndex(
  [
    'John', 
    'Jack', 
    'James', 
    'Jason',
    'Jerome',
    'Jameson',
    'Jamar',
    'Jabar'
  ], 
  'John'
)

...然后将数组中的项目加倍不一定会导致函数的运行时间加倍，因为它会跳出循环并在第一次迭代后返回.因此，那么说 getArrayItemIndex 函数具有对数时间复杂度是否准确？

Answer 1

不完全是。你在这里拥有的是线性搜索。它最差的 ccase 性能是 Theta(n)，因为如果搜索目标不在列表中，它必须检查所有元素。您发现它的最佳性能是 Theta(1)，因为如果幸运的话，该算法只需运行几次检查。

对预先排序的数组进行二分查找是 O(log n) 最坏情况算法的一个例子（最好情况仍然是 O(1)）。它是这样工作的：

检查中间元素。如果匹配，return。否则，如果元素太大，则对数组的前半部分进行二分查找。如果太大，则在后半部分进行二分查找。继续，直到找到目标或运行没有要检查的新元素。

在二进制搜索中，我们从不查看所有元素。这就是区别。

Is this an example of logarithmic time complexity?