'Divide and conquer' 是否为未排序的数组产生 O(log N)？

Question

以下算法找到最大 QAZ。元素的 QAZ 是在该元素的索引之后具有更高值的元素的数量。流行的答案是使用除法并使用 O(nLog(n))..

求解

数组未排序。在最坏的情况下 'Divide&Conquer' 将触及所有 n 个元素。另外 'for loop' 会触及 n/2 更糟的元素.. n*log(n) 怎么样.. 不应该是 O(n^2).. 谢谢

class QAZ:
    def __init__(self, min, qaz):
        self.min = min
        self.qaz = qaz


def max_qaz(arr):
    n = len(arr)

    def max_qaz_util(start, end):
        if end <= start:
            return QAZ(arr[end], 0)
        elif start == (end + 1):
            return QAZ(arr[start], 1) if arr[start] < arr[end] else QAZ(arr[end], 0)
        mid = int((start + end) / 2)
        left = max_qaz_util(start, mid)
        right = max_qaz_util(mid + 1, end)
        if left.min < right.min:
            left.qaz += end - mid
            return left
        else:
            for i in range(mid + 1, end + 1):
                if arr[i] > left.min:
                    left.qaz += 1
        return left if left.qaz > right.qaz else right

    result = max_qaz_util(0, n - 1)
    print("minval", result.min)
    print("qaz", result.qaz)

max_qaz([33, 25, 26, 58, 41, 59])

参考 - https://shirleyisnotageek.blogspot.com/2015/02/find-maximum-qaz.html?showComment=1481295499335#c2817927984213209920

Answer 1

是的，在最坏的情况下，for 循环会触及 n/2 个元素。这里的重要事实是输入的划分尽可能均匀。算法在 n 个元素上完成的工作量为 O(T(n))，其中重复 T 由

定义

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

Master Theorem 的情况 2 适用，因此 T(n) = O(n log n)。这与归并排序非常相似。

'Divide and conquer' 是否为未排序的数组产生 O(log N)？

Does 'Divide and conquer' yield O(log N) for unsorted array?

algorithm

recursion

divide-and-conquer