algorithm - 对于未排序的数组，“划分并征服”会产生O(log N)吗？

下面的算法找到max QAZ元素的qaz是元素索引之后具有更高值的元素数。普遍的答案是用O（nLog（n））进行除法和求解。。
数组未排序在最坏的情况下，“分而治之”会触及所有的n个元素。“for loop”也会在更糟的情况下接触n/2个元素。你好吗？日志…不应该是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

最佳答案

是的，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)。这与合并排序非常相似。