«Разделяет и побеждает» дает O (log N) для несортированного массива?

Question

Следующий алгоритм находит max QAZ. QAZ элемента - это число элементов с более высоким значением после индекса этого элемента. Популярным ответом является использование divide и решение с использованием O (nLog (n)).

Массив не отсортирован. В худшем случае «Divide & Conquer» коснется всех 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

Answer 1

Да, петля для петли касается n/2 элементов в худшем случае. Важным фактом здесь является то, что разделение ввода как можно более возможно. Объем работы, проделанной с помощью алгоритма на n элементов O(T(n)), где повторение T определяется

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

Случай 2 Master Theorem применяется, так T(n) = O(n log n). Это очень похоже на сортировку слияния.