python - 这个特定算法的运行时间是多少？

Question

我认为这个特定的代码是 (log n)^2 因为每个 findindex 函数都需要 logn 深度并且我们称它为 logn 次？有人可以证实这一点吗？ 我希望你们中的任何一个人可以将此视为一个小测验并帮助我完成它。

Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element in the array. You may assume that the array was originally sorted in increasing order.

# 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

Answer 1

这个算法应该是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))