Zeit Komplexität des Algorithmus zum Sortieren von Namen mit der Bubble-Sortierung

-1

Eine Maschine dauerte 200 Sekunden, um 200 Namen mit der Bubble-Sortierung zu sortieren. Dann in 800 Sekunden, wie viele Namen sortiert werden. Bitte helfen Sie mir, dies zu lösen. Ich versuchte es mit der Zeit Komplexität der Blase Art zu lösen, aber ich bin nicht in der Lage esZeit Komplexität des Algorithmus zum Sortieren von Namen mit der Bubble-Sortierung

zu tun und will auch die Komplexität des folgenden Codes finden

int somefunct(int n) 
    { 
     if(n<=2) 
     return 1; 
     else 
     return (somefunct(floor(sqrt(x)))+x); 
    }

Quelle

2016-06-27 maddy

800 = 4 * 200; sqrt (4) = 2, so dass Sie doppelt so viele wie zuvor sortieren können (400 Namen). – maraca

Wie lange sind die Namen? Was ist die Wahrscheinlichkeit, dass 1 Buchstabe gleich ist, 2 Buchstaben gleich sind usw.? Ohne solche Informationen ist wirklich schwer zu schätzen, es sei denn, Sie vermuten, String-Vergleich ist in 'O (1)' getan ... Auch ohne den Zustand der Unordnung Ihrer Daten ist schwer zu sagen ... Komplexität der Blase Sortierung ist "O (n^2) 'aber das ist nur für umgekehrt geordnete Daten, die höchst unwahrscheinlich sind. Sie müssen also wirklich WILDE ANNAHMEN hinzufügen, um diese – Spektre

Die Komplexität der Blase Sortierung ist O(n^2) im schlimmsten Fall. Also in 4 mal die gegebene Zeit wird es zweimal die gegenwärtigen Namen sortieren. dh. Im schlimmsten Fall 400 Namen in 800 Sekunden.

Quelle

2016-06-27 09:58:01

Da die Zeit durch eine Blase-Art im schlimmsten Fall zu sortieren ein Polynom vom Grad 2 in n ist, haben wir:

t = an^2 + bn + c

Jetzt, da n groß genug ist (200 hier) , so können wir die letzten beiden Begriffe zu bekommen ignorieren:

t = an^2

die Werte Put: t = 200 und n = 200a = 1/200

01 zu erhalten

Daher wird in 800 Sekunden, werden Sie in der Lage sein, zu sortieren atmost: atmost

800 = (1/200)*(n^2)

=> n = 400 Namen

weil dies der schlimmste Fall ist.

Quelle

2016-06-27 11:01:14

Sorry Jim zu berechnen, ich habe es verpasst. Bearbeitete die Antwort jetzt. –

O (n^2) bedeutet nicht, dass die exakte Formel ein Polynom ist. Zum Beispiel könnte es 't = a * n^2 + b * n * log (n) oder etwas noch seltsamer sein. (Natürlich ist Ihre Logik ansonsten korrekt, dass der n^2 Begriff die anderen Begriffe schließlich dominieren wird und das ist klar, was diese Hausaufgabenfrage beabsichtigt.) –

Ja, Sie haben Recht, ich werde die Schreiblogik korrigieren. Obwohl für eine Blasensortierung die Polynomrelation gelten wird. –

Für die Sortierung von 200 Namen macht Bubble Sort 200 * 199/2 = 19900 Vergleiche.
Die Zeit für einen Vergleich beträgt 200 Sekunden. In 800 Sekunden kann es 80.000 Vergleiche machen.
Wir müssen n finden, so dass n (n-1)/2 = 80.000. => n^2 - n = 160000. Der letzte Term kann vernachlässigt werden. Daher ist n^2 = 160000. Antwort = 400.

Quelle

2016-06-28 08:11:17

* "Die Zeit, die für einen Vergleich benötigt wird, beträgt 200 Sek." * Ich bin sicher, Sie haben etwas anderes gemeint, denn wenn ein Vergleich 200 Sekunden dauert, können Sie nur vier Vergleiche in 800 Sekunden durchführen. In jedem Fall ist es nicht wirklich notwendig, Vergleiche zu zählen, wenn Sie das Problem einfach genug lösen können, indem Sie nur die Zeit und die geschätzte algorithmische Komplexität verwenden (n^2). –

Zeit Komplexität des Algorithmus zum Sortieren von Namen mit der Bubble-Sortierung

Antwort

Verwandte Themen