Что такое большой нить этого псевдокода? Мне также нужно надлежащее объяснение

Это псевдокод, который я хочу вычислить по временной сложности, я думаю, что это алгоритм двоичного поиска, но я не могу вычислить сложность, потому что он уменьшает логарифмическую.

   USE variables half-array,found,middle element
   SET half-array=initial array;
   SET found=True;

 Boolean SearchArray(half-array)

   find middle element in half-array;
   Compare search key with middle element;
   IF middle element==search key THEN
           SET found=True;
   ELSE
        IF search key< middle element THEN
          SET half-array=lower half of initial array;
        ELSE
          SET half-array=upper half of initial array;


 SearchArray(half-array)

java algorithm big-o pseudocode
person kalsara Magamage    schedule 26.04.2017    source источник
comment
Вы запускаете метод только один раз или используете его рекурсивно?   -  person obizues    schedule 26.04.2017
comment
запустить его рекурсивно   -  person kalsara Magamage    schedule 26.04.2017
comment
его бинарный поиск, log (n)   -  person nafas    schedule 26.04.2017
comment
Похоже, вы запускаете этот метод рекурсивно, и с каждой итерацией вы вдвое уменьшаете количество элементов, в которых выполняется поиск. Это будет логарифмическое сокращение, то есть O (log n).   -  person Rion Williams    schedule 26.04.2017
comment
Какой ответ? Это O (журнал N)   -  person kalsara Magamage    schedule 26.04.2017
comment
@kalsaraMagamage, как заявили Рион и Нафас, да, это так   -  person XtremeBaumer    schedule 26.04.2017
comment
stackoverflow.com/questions/10369563/ Думайте о O (n) как о единственном перечислении в Списке размера n. O (log n) будет, когда алгоритм намного более эффективен и не перечисляет весь список, но использует логику для более быстрого поиска ответа, как в двоичном поиске   -  person Novaterata    schedule 26.04.2017
comment
Возможный дубликат метода расчета сложности двоичного поиска   -  person xandermonkey    schedule 26.04.2017
comment
Это O(42). Почему? Потому что 42 - это ответ на все вопросы, доступные во вселенной.   -  person Harmlezz    schedule 26.04.2017
comment
Заучивание ответов на один вопрос за раз не научит вас. Вам необходимо приобрести и изучить en.m.wikipedia.org/wiki/Introduction_to_Algorithms   -  person Lew Bloch    schedule 26.04.2017

Ответы (3)


arrow_upward
3
arrow_downward

Похоже, вы запускаете этот метод рекурсивно, и с каждой итерацией вы вдвое уменьшаете количество элементов, в которых выполняется поиск. Это будет логарифмическое сокращение, то есть O (log n).

Поскольку вы каждый раз уменьшаете количество элементов вдвое, вам необходимо определить, сколько выполнений потребуется, чтобы уменьшить его до одного элемента, который этот предыдущий ответ является доказательством, или, если вы более наглядный человек, вы можете использовать следующую диаграмму из этого ответа :

введите здесь описание изображения

person Rion Williams    schedule 26.04.2017
comment
Могу я написать такой ответ, log / ln N - person kalsara Magamage; 26.04.2017
comment
Вы бы просто написали это как O(logN). Обозначение Big O обычно игнорирует любые коэффициенты, поэтому, если они были (например, O(2N) == O(N)). - person Rion Williams; 26.04.2017
comment
Нет, вы бы также проигнорировали любую специфику, касающуюся баз (например, O(log2N) == O(logN)). Экспоненты - единственное исключение из этого правила, поскольку O(N^2) сильно отличается от O(N^3). - person Rion Williams; 26.04.2017

arrow_upward
0
arrow_downward

Да, это действительно алгоритм двоичного поиска. Причина, по которой он называется `` двоичным '' поиском, заключается в том, что, если вы заметили, после каждой итерации ваше проблемное пространство уменьшается примерно наполовину (я говорю примерно из-за пола функция). Итак, теперь, чтобы найти сложность, мы должны разработать рекуррентное соотношение, которое мы можем использовать для определения наихудшей временной сложности двоичного поиска.

Пусть T (n) обозначает количество сравнений, выполняемых двоичным поиском для n элементов. В худшем случае ни один элемент не найден. Кроме того, чтобы упростить наш анализ, предположим, что n является степенью двойки.

ДВОИЧНЫЙ ПОИСК:

  1. Когда есть один элемент, есть только одна проверка, поэтому T (1) = 1.

  2. Он вычисляет среднюю запись, затем сравнивает ее с нашим ключом. Если он равен ключу, он возвращает индекс, в противном случае он сокращает диапазон вдвое, обновляя верхнюю и нижнюю границы так, чтобы в диапазоне было n / 2 элементов.

  3. Затем мы проверяем только одну из двух половин, и это делается рекурсивно, пока не останется единственный элемент.

Отсюда получаем рекуррентное соотношение:

T (n) = T (n / 2) + 1

Используя основную теорему, мы получаем временную сложность T (n) ∈ Θ (log n)

См. Также: Основная теорема

person Ashwin Nalwade    schedule 26.04.2017

arrow_upward
0
arrow_downward

Вы правы, говоря, что это алгоритм двоичного поиска (сравните свой псевдокод с псевдокодом на этой странице Википедии: Двоичный поиск)

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

Этот процесс сокращения является логарифмическим, потому что в конце этого алгоритма вы сократите список до одного элемента, разделив количество элементов, которые все еще необходимо проверить, на 2 - количество раз, которое вы делаете это примерно эквивалентно (см. ниже) на количество раз, которое вам нужно было бы умножить 2 на себя, чтобы получить число, равное размеру данного массива.

* Я сказал примерно выше, потому что количество сделанных рекурсивных вызовов всегда будет целым значением, тогда как мощность, которую вам нужно будет увеличить до 2, не будет целым числом, если размер данного списка это не степень двойки.

person Trevor Maliborski    schedule 26.04.2017