Verwirrt über diese asymptotische Notation und ihre Laufzeit

Question

public static Asymptotic f3_notation = Asymptotic.BIG_THETA; 
public static Runtime f3_runtime = Runtime.LINEAR; 
/* When f3 is first called, start will be 0 and end will be the length of the array - 1 */ 
public int f3(char[] array, int start, int end) { 
    if (array.length <= 1 || end <= start){ 
     return 1; 
    } 

    int mid = start + ((end - start)/2); 

    return f3(array, start, mid) + f3(array, mid + 1, end); 
} 

public static Asymptotic f4_notation = Asymptotic.BIG_THETA; 
public static Runtime f4_runtime = Runtime.LINEARITHMIC; 
/* When f4 is first called, start will be 0 and end will be the length of the array - 1 */ 
public int f4(char[] array, int start, int end) { 
    if (array.length <= 1 || end <= start) return 1; 

    int counter = 0; 

    for (int i = start; i < end; i++) { 
     if (array[i] == 'a') counter++; 
    } 

    int mid = start + ((end - start)/2); 

    return counter + f4(array, start, mid) + f4(array, mid + 1, end); 
} 

So habe ich diese beiden Methoden. Was ich nicht verstehe ist, dass beide Rekursionen haben, aber warum ist der erste linear und die zweite Methode linear? Mir wurde gesagt, dass, wenn es Division oder Multiplikation gibt, normalerweise seine Laufzeit log-n ist. Obwohl die erste Methode die Division hat, wird sie immer noch als linear betrachtet, die zweite jedoch nicht.

Je mehr ich verstehe, desto mehr verwirrt es mich und lässt mich fühlen, dass ich nichts weiß.

Answer 1

Die Formel für die erste Methode ist:

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

Also, wenn man die entsprechende Struktur für diese Formel ziehen wird man sehen, dass Die Menge an Arbeit ist proportional zur Anzahl der Knoten im Baum, der O (n) ist. Sie könnten auch Master Method verwenden, um dies zu lösen.

Aber für die zweite ist:

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

In der Tat, was hier passiert ist, dass Ihr Baum (nur haben wird wie die erste Methode) O (log n) Ebenen, aber hier in jeder Ebene verbringen Sie O (n) Zeit, was zu O (n log n) Zeit Komplexität führt. Auch hier arbeitet Master Theorem. Beachten Sie, dass im ersten Fall Ihr Baum (für die Formel) O (log n) -Ebenen hat, aber in jedem Level werden Sie die Zeit proportional zur Anzahl der Knoten auf dieser Ebene und nicht O (n) verbringen.