Какова временная сложность в двоичном поиске?

#python #time-complexity #big-o #binary-search

#python #временная сложность #big-o #двоичный поиск

Вопрос:

 def binsearch(a):
    if len(a) == 1:
        return a[0]
    else:
        mid = len(a)//2
        min1 = binsearch(a[0:mid])
        min2 = binsearch(a[mid:len(a)])
        if min1 < min2:
            return min1
        else:
            return min2

Я попытался определить временную сложность для min1 < min2, и я чувствую, что это O (n), но я не очень уверен, правильно ли это. Может кто-нибудь, пожалуйста, попытаться объяснить мне, как рассчитать временную сложность для такого кода?

1. Вы имеете в виду конкретно строку if min1 < m2 , какова временная сложность этой одной строки? Или вы спрашиваете о временной сложности всей функции?

2. @JohnKugelman в частности, строка: (

3. Что a такое список чисел?

4. @JaeYing Я не заметил, что ваша функция на самом деле не является двоичным поиском. Ваша функция O(n) . В то время min1 < min2 как как одно выражение O(1) .

5. @JaeYing Это называется двоичным поиском, но на самом деле внутри каждого вызова функции он выполняет одно сравнение плюс обрабатывает две части размера n/2 , оба n в общем размере. Таким образом, в основном это не уменьшает вдвое размер обрабатываемого массива, как это делает двоичный поиск.

Ответ №1:

Если min1 и min2 являются числами, и их всегда 2 (константа), объем работы над этой конкретной строкой (одно сравнение) никогда не меняется. Следовательно, его временная сложность O(1) .

Однако может измениться количество раз, когда выполняется эта строка! Когда у вас есть n время O(1) для операции, общая временная сложность остается прежней O(n) .

1. Какова временная сложность операции сращивания? Это O (1) или O (n)? В зависимости от этого, этот алгоритм либо O (n), либо O (n log N) .

2. @FrankYellin Этот алгоритм строит дерево двоичного поиска. У него N листьев. И N-1 внутренних узлов. Учитываются только операции с внутренними узлами, сравнение min1 < min2 , листья не выполняют сравнения. Итак, общая сложность O(N) . Конечно, это несколько амортизируется операциями рекурсивных вызовов функций. Нарезка также выполняется внутри внутренних узлов. Так что, возможно, точная сложность заключается в O(4N) том, что это просто O(N) .

3. Полагаю, я не уверен, в чем вопрос. Какова временная сложность этого алгоритма или сколько раз вызывается min1 < min2? O (n log n) и O (n) соответственно (при условии, что операция соединения равна O (<количество элементов>).

4. @sabik Да, если это список python, который, вероятно, является тогда нарезкой, является дорогостоящим, если это массив numpy, который, вероятно, нет (потому что целая функция не ориентирована на numpy), тогда это вызывает легкий вес.

5. @JaeYing Кстати, всю вашу функцию можно заменить просто result = min(a) встроенным вызовом функции, на самом деле это будет намного эффективнее.