Algorithmen und Datenstrukturen · Middle · Frage 64 von 75
Welche Komplexität hat diese Funktion?
function f(n) {
if (n <= 1) return 1;
return f(n / 2) + f(n / 2);
}- 1O(log n)
- 2O(n log n)
- 3O(n)
Antwort zeigen
Richtige Antwort: O(n)
Erklärung
Jeder Aufruf macht zwei Aufrufe mit der halben Eingabe, der Aufrufbaum hat also 1 + 2 + 4 + ... + n ≈ 2n Knoten mit je O(1) Arbeit. Mit nur einem Aufruf, f(n / 2) allein, wäre es O(log n).