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

Question

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

考虑到这一点，我有一个函数，该函数将字符串数组作为第一个参数，并将单个字符串作为第二个参数，并返回该字符串在数组中的索引：

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

并且可以说该函数的调用如下：

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

在这种情况下，该函数在返回1的索引之前不会最终遍历整个数组。同样，如果我们将数组中的项目加倍，以使其最终被调用，如下所示：

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

...然后加倍数组中的项并不一定会使函数的运行时间加倍，因为它会脱离循环并在第一次迭代后返回。因此，准确地说getArrayItemIndex函数具有对数时间复杂度吗？

Answer 1

不完全是。您在这里拥有的是线性搜索。它的最坏情况是Theta（n），因为如果搜索目标不在列表中，则它必须检查所有元素。您发现的是它的最佳情况下的性能是Theta（1），因为如果幸运的话，该算法只需运行一些检查即可。

对预排序数组的二进制搜索是O（log n）最坏情况算法的一个示例（最佳情况仍然是O（1））。它是这样的：

检查中间元素。如果匹配，请返回。否则，如果元素太大，则对数组的前半部分执行二进制搜索。如果太大，请在下半部分执行二进制搜索。继续直到找到目标或用尽新元素进行检查。

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