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.
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
Link
geantwortet
stal
Punkte: 11.27K
Punkte: 11.27K
Ich Küss deine Augen es macht alles Sinn. Ich danke dir!
─
user7b4d48
19.04.2021 um 17:55