Wie berechnet man hiervon den Aufwand ?

Erste Frage Aufrufe: 40     Aktiv: 19.04.2021 um 17:55
1
Berechne doch mal die ersten paar Terme: 1,3,7,15,31,... Fällt dir bei denen ein Muster auf? (Tipp: Addiere immer 1) Wenn du das Muster erkannt hast, kannst du dieses mit vollständiger Induktion zeigen. Alternativ gibt es bestimmt irgendein Mastertheorem, das diesen Fall abdeckt, aber ich kann mir die nicht alle merken.
Schon bevor du den genauen Aufwand berechnet hast, solltest du erkennen, dass sich der Aufwand bei jedem Schritt ungefähr verdoppelt, also solltest du etwas in \(\mathcal O(2^n)\) erwarten.
Diese Antwort melden
geantwortet

Punkte: 7.64K
 

Ich Küss deine Augen es macht alles Sinn. Ich danke dir!   ─   user7b4d48 19.04.2021 um 17:55

Kommentar schreiben