Каково время выполнения для этого конкретного алгоритма? - PullRequest
Новая
       6

Каково время выполнения для этого конкретного алгоритма?

0 голосов
/ 24 мая 2018

Я думаю, что этот конкретный код (log n) ^ 2, потому что каждая функция findindex занимает глубину logn, и мы вызываем ее logn times?Кто-нибудь может это подтвердить?Я надеюсь, что один из вас может подумать об этом как о небольшом тесте и помочь мне с ним.

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

# Ex
# input find 5 in {15,16,19,20,25,1,3,4,5,7,10,14}
# output 8
# runtime(log n)


def findrotation(a, tgt):
    return findindex(a, 0, len(a)-1, tgt, 0)


def findindex(a, low, high, target, index):
    if low>high:
        return -1

    mid = int((high + low) / 2)

    if a[mid] == target:
        index = index + mid
        return index
    else:
        b = a[low:mid]
        result = findindex(b, 0, len(b)-1, target, index)
        if result == -1:
            index = index + mid + 1
            c = a[mid+1:]
            return findindex(c, 0, len(c)-1, target, index)
        else:
            return result

1 Ответ

0 голосов
/ 24 мая 2018

Предполагается, что этот алгоритм равен O(logn), но не с точки зрения реализации.

  • В вашем алгоритме вы не принимаете решение о переходе на левый или правый подмассив.только вы пытаетесь использовать оба подмассива: O(N).

  • Вы делаете нарезку на массиве a[low:mid] и a[mid + 1:], что составляет O(n).

Что делает вашу общую сложность O(n^2) в худшем случае.

Если предположить, что в массиве нет дубликатов, идеальная реализация в Python 3 двоичного поиска O(logn) выглядит следующим образомэто - 

A=[15,16,19,20,25,1,3,4,5,7,10,14]
low = 0
hi = len(A) - 1


def findindex(A, low, hi, target):
    if low > hi:
        return -1
    mid = round((hi + low) / 2.0)
    if A[mid] == target:
        return mid
    if A[mid] >= A[low]:
        if target < A[mid] and target >= A[low]:
            return findindex(A, low, mid - 1, target)
        else : 
            return findindex(A, mid + 1, hi, target)

    if A[mid] < A[low]:
        if target < A[mid] or target >= A[low]:
            return findindex(A, low, mid - 1, target)
        else :
            return findindex(A, mid + 1, hi, target)

    return -1

print(findindex(A, low, hi, 3))
...