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.

Themen

Beweis für Laufzeit nlogn

Gast Odi1981
Gast Odi1981
in Algorithmik

Empfohlene Antworten

Veröffentlicht

Wie kann ich beweisen, das ein Algorithmus wie QuickSort oder MergeSort nicht schneller als nlogn arbeiten kann ??

Danke Odi

QuickSort

Na ja anhand des Programmablaufes stellst du einfach die Zeitkomplexität auf.

Für den ist es

(n log(n)) im Durchschnitt und

(n2) im schlechtesten Fall

Nu ja und jetzt musst du nur noch zeigen das dies immer schlechter ist als deins sein kann. (was aber eben nur im Mittel stimmt, und im optimum eben schon)

Wenn du nicht weist was o(n) ist, ....

Archiv

Dieses Thema wurde archiviert und kann nicht mehr beantwortet werden.

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.