Алгоритм поиска и его сложность - PullRequest
Новая
       12

Алгоритм поиска и его сложность

7 голосов
/ 16 марта 2011

Мне задали этот вопрос в интервью: предположим, что бесконечный массив целых чисел, который отсортирован.Как бы вы искали целое число в этом массиве?Какова будет сложность времени?Я догадался, что интервьюер имел в виду под бесконечностью, что мы не знаем значение 'n', где n - это индекс наибольшего числа в массиве.Я дал следующий ответ: 

SEARCHINF(A,i,x){ // Assume we are searching for x
if (A(1) > x){
   return
}
if(A(i) == x){
   return i;
}
else{
    low = i;
    high = power(2,i);
    if (A(i)>x){
       BINARY-SEARCH(A,low,high);
    }
    else{
        SEARCHINF(A,high,x);
    }
}// end else
}// end SEARCHINF method

Это найдет предел (низкий и высокий) в (log x + 1) времени в худшем случае, когда отсортированные числа начинаются с 1, а последующие числа являются последовательными,Тогда бинарный поиск требует: 

O( log {2^(ceil(log x)) - 2^(floor(log x))} )

Это правильно?Если правильно, можно ли это оптимизировать?

Ответы [ 2 ]

4 голосов
/ 16 марта 2011

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

Потребуется (log 2 n) попытаться найти правильный регион, а затем ((log 2 n) - 1) попытается найти x в этом регион (так как вы уже искали от 0..n / 2, вам нужно только искать n / 2..n). Следовательно, O (log 2 n + log 2 n - 1) = O (log 2 n).

Однако, если «бесконечный массив» не содержит x или любое значение, большее, чем x, вы никогда не узнаете, потому что вы будете искать вечно.

1 голос
/ 16 марта 2011

Сортированный массив действительно выдает его: двоичная сортировка.

В худшем случае: O (lg (n)).Нет более быстрого и надежного способа его найти.

Конечно, вы можете просто сказать ему, что поиск элемента в бесконечном массиве займет вечность.

...