Algorithmen und Datenstrukturen · Senior · Frage 23 von 75
Welche Komplexität hat nach dem Master-Theorem T(n) = 2T(n/2) + O(n)?
- 1O(n) wie eine einzige Schleife
- 2O(n²) wegen zwei Aufrufen
- 3O(n log n)
Antwort zeigen
Richtige Antwort: O(n log n)
Erklärung
Zwei Hälften mit linearer Arbeit zum Kombinieren sind die Rekurrenz von Merge Sort. Jede der log n Rekursionsebenen macht insgesamt O(n) Arbeit. T(n) = 2T(n/2) + O(1) wäre O(n), und T(n) = T(n/2) + O(1) ist binäre Suche, O(log n).