Wenn ich einen Algorithmus habe, wo ein Teil von ihm Komplexität hat-O (nlogn) und ein Teil davon hat Komplexität big-O (n). Was wäre die endgültige Komplexität des Algorithmus? Soweit ich weiß, wäre es groß-O (nlogn).Mehrere Komplexitäten
Sie haben recht, der schlimmste mögliche Fall zählt, in Ihrem Fall o (nlog (n)).
Ich hatte eine Follow-up-Frage zu diesem Thema, wenn es Ihnen nichts ausmacht? Ich habe einen Algorithmus mit der laufenden Komplexität O (nlogn) und einen mit O (n^2). Ich ließ sie beide mit Proben von 1 bis 5000 laufen und zeichnete die für jede Probe benötigte Zeit auf. Was ich seltsam fand, ist, dass mit zunehmender Stichprobengröße die mit O (n^2) schneller wurde als die O (nlogn). Kann das passieren oder sind die Chancen, dass ich die zeitliche Komplexität falsch ausarbeite? –
Nein, ich denke nicht, dass es möglich ist, können Sie die Grafiken der Funktionen vergleichen, um für sich selbst zu sehen, die horizontale Achse werden die Eingaben sein, die Sie überprüfen, und die vertikale wird die Laufzeit der Eingabe currespondimg sein. –
Es hängt davon ab, was Sie unter „Teil davon“ bedeuten ...
Nehmen wir an, Sie eine for-Schleife, die eine Komplexität von O (n) und eine binäre Suche nach O (log n) hat
Wenn Sie Programm wie folgt aussehen:
for(int i=0; i < n; i++) { // O(n)
/// some stuff here
}
binarySearch(); // O(logn)
Zeitkomplexität wäre O (n)
Howe ver wenn haben diese Situation:
for(int i=0; i < n; i++){ // O(n)
binarySearch(); // O(n * logn)
}
Zeitkomplexität wäre O (n log n)
Edit:
Wenn der Algorithmus von verschiedenen Blöcken mit unterschiedlicher Zeit Komplexität zusammengesetzt ist, dann Algorithmus Zeitkomplexität = max (O (Block1), O (Block2), ...)
Ich habe tatsächlich eine sehr ähnliche Situation, eine for-Schleife der Komplexität O (n) und eine Art von O (nlogn). Aber die Art geschieht unabhängig von der Schleife. –
@BarryS Überprüfen Sie die Bearbeitung – CMPS
Was ist Ihr Algorithmus? Bitte verstecken Sie keine kritischen Dinge vor uns. – HuStmpHrrr