Komplexitätsberechnung Aufgabennachfrage

Aufrufe: 451     Aktiv: 28.07.2023 um 09:15

0

Hey, ich bin mir unsicher, ob meine Lösungen zu den beiden Aufgaben richtig sind.

Bei der ersten Aufgabe steht eine alternative Lösung zur Debatte und zwar: k × (l ×2) = 2×k×l = 2×n O(2n) = O(n)

Die alternative Lösung kommt daher, dass man die Eingabegröße beachtet. Ich dachte man muss das komplett ignorieren bei der Komplexitätsberechnung, bin mir aber trotzdem unsicher, vielleicht eine Erwähnung zur Verwirrung??

Bei der zweiten Aufgabe bin ich mir ziemlich sicher, dass es falsch ist, habe aber keine Ahnung wie ich es anders formal herleiten würde. Als Idee käme mir nur ein c und ein n0 zu finden, aber ehrlich gesagt keine Ahnung wie das gehen soll.

meine erste Lösung

Diese Frage melden
gefragt

Punkte: 12

 

Deine Idee bei der zweiten Aufgabe ist auf jeden Fall richtig. Versuche doch mal c=3 zu wählen. Dann musst du nur noch ein n_0 finden so dass f(n) <= c g(n) für alle n >= n_0 gilt.

  ─   jordan 28.07.2023 um 09:07
Kommentar schreiben
0 Antworten