Zum Inhalt springen
View in the app

A better way to browse. Learn more.
Fachinformatiker.de

A full-screen app on your home screen with push notifications, badges and more.

To install this app on iOS and iPadOS
  1. Tap the Share icon in Safari
  2. Scroll the menu and tap Add to Home Screen.
  3. Tap Add in the top-right corner.
To install this app on Android
  1. Tap the 3-dot menu (⋮) in the top-right corner of the browser.
  2. Tap Add to Home screen or Install app.
  3. Confirm by tapping Install.

Nochmals O-Notation

buzz_lightzyear
in Prüfungsaufgaben und -lösungen

Empfohlene Antworten

Veröffentlicht

Hallo nochmal,

ich hab gleich noch eine Frage zu einem anderen Beispiel und zwar gehts hier um die Fibonacci-Folge (rekursiv).

Die Rekursionsgleichung dazu lautet:

T(n)=O(1) + T(n - 1) + T(n - 2)=                           //Rekursionsgleichung, alles klar

=O(1) + O(1) + T(n - 2) + T(n - 3) + T(n - 2) 

Hier hab ich ein kleines Verständnisproblem und zwar:

Ich bin hier einen Rekursionsschritt tiefer, sprich ich habe (n-1) für n in die erste Gleichung eingesetzt -> ok!

Aber woher kommt das letzte T(n - 2)? Das kann ich nicht nachvollziehen... :-(

Jemand einen Tipp für mich? :-)

Thx & Lg

buzz

 

Erstelle ein Konto oder melde dich an, um einen Kommentar zu schreiben.

https://www.fachinformatiker.de/topic/156770-nochmals-o-notation/
Zur Themenliste gehen

Configure browser push notifications
Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.