Это пример логарифмической c сложности времени?

Question

Обычно говорят, что алгоритм с логарифмией c сложность по времени O(log n) - это алгоритм, в котором удвоение входных данных не обязательно удваивает объем требуемой работы. И часто, алгоритмы поиска приводятся в качестве примера алгоритмов со сложностью логарифми c.

Имея это в виду, допустим, у меня есть функция, которая также принимает массив строк в качестве первого аргумента. в качестве отдельной строки в качестве второго аргумента, и возвращает индекс строки в массиве:

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'
)

... тогда удвоение элементов в массиве не обязательно вызвало бы время выполнения двойной функции, видя, что она вышла бы из l oop и вернулась после самой первой итерации. Из-за этого, тогда правильно ли говорить, что функция getArrayItemIndex имеет логарифмическую c сложность по времени?

Answer 1

Не совсем. Здесь у вас есть Линейный поиск. Его худшая производительность - Theta (n), поскольку он должен проверять все элементы, если цель поиска отсутствует в списке. Что вы обнаружили, так это то, что его лучшая производительность - это Theta (1), так как алгоритм должен выполнить только несколько проверок, если вам повезет.

Двоичный поиск по предварительно отсортированным массивам является примером O (log n) алгоритм наихудшего случая (лучший случай все еще O (1)). Это работает так:

Проверьте средний элемент. Если это совпадает, вернитесь. В противном случае, если элемент слишком большой, выполните бинарный поиск в первой половине массива. Если он слишком большой, выполните бинарный поиск во второй половине. Продолжайте, пока не найдете цель или не исчерпаете новые элементы для проверки.

В бинарном поиске мы никогда не смотрим на все элементы. В этом разница.