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

问题描述

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

给定一个已旋转未知次数的 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

标签： pythonalgorithmruntimebig-o

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

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

问题描述

解决方案

推荐阅读