Gibt 'Divide and Conquer' O (log N) für unsortiertes Array?

Question

Der folgende Algorithmus findet max QAZ. QAZ eines Elements ist die Anzahl der Elemente mit einem höheren Wert nach dem Index dieses Elements. Die gängige Antwort ist die Verwendung von Teilen und Lösen mit O (nLog (n)).

Das Array ist nicht sortiert. Im schlimmsten Fall wird 'Divide & Conquer' alle n Elemente berühren. Auch n/2 Elemente bei schlechter .. Wie ist es n * log (n) .. Sollte es nicht sein O (n^2) .. Dank

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]) 

Reference 'for-Schleife' berühren - https://shirleyisnotageek.blogspot.com/2015/02/find-maximum-qaz.html?showComment=1481295499335#c2817927984213209920

Answer 1

Ja, die for-Schleife berührt n/2 Elemente im schlimmsten Fall. Die wichtige Tatsache hier ist, dass die Aufteilung der Eingabe so gleichmäßig wie möglich ist. Die Menge an Arbeit, die durch den Algorithmus durchgeführt auf n Elementen O(T(n)), wo das Wiederauftreten von T

definiert

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

Fall 2 der Master Theorem gilt, so T(n) = O(n log n). Dies ist sehr ähnlich zu merge sort.