Zeitkomplexität Algorithmus von Kruskal?

Ich habe den Algorithmus von Kruskal in Python programmiert. Bin mir aber bei seiner Zeitkomplexität unschlüssig. Im Internet habe ich gefunden, dass diese O(|E|*log(|E|)) sei. Wobei E die Anzahl an Kanten ist. Kann mir das jemand erklären?

Jangler13

12.10.2023, 14:29

Was genau ist dir unklar?

ZekeZeke

Fragesteller

12.10.2023, 14:38

Ich verstehe nicht, wie man auf dieses Ergebnis kommt. Kann man das irgendwie herleiten?

1 Antwort

NoArtFX

12.10.2023, 14:51

Das Sortieren dauert O(n log(n)) oder eben O(|E| log(|E|).

Danach musst du ja nur noch jedes Element genau 1 Mal anschauen, um zu prüfen, ob du es in deinen MST hinzufügen kannst oder nicht. Also noch O(1). Da O(|E| log(|E|) > O(1) ist das deine Zeitkomplexität.

Woher ich das weiß:Studium / Ausbildung – Bachelor-Student in Informatik

Ähnliche Fragen

Was ist ein optimaler Algorithmus?

Hallo,

Ich suche momentan nach der Begriffsklärung für die Eigenschaft "optimal" in Bezug auf Algorithmen. Ich kann die antwort leider nur zum Beispiel in dieser Form finden:

Unter der Zeitkomplexität eines Problems wird in der Datenverarbeitung die Anzahl der Rechenschritte verstanden, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. (Von Wikipedia)

Da steht aber nirgends was denn nun Optimal bedeutet. Weiß das jemand?

...zur Frage

Wurzelberechnung graphisch mit Python?

Hallo.

Das Ziel vom Programm ist, mir eine Graphik der Wurzelberechnung zu zeigen. Ich habe das Programm in Python programmiert, aber ich verstehe nicht mehr ganz was ich genau gemacht habe. Zudem verstehe ich nicht weshalb die Listen x=[ ] & y=[ ] leer sind.

Ich wäre froh wenn jemand mir erklären könnte was das Programm macht (muss nicht Schritt für Schritt erklärt werden, einfach allgemein und das mit x=[ ]).

...zur Frage

Bäume/Informatik/Tiefensuche: Wie funktioniert die in-order-Traversierung?

Ich verstehe die in-order bei der Traversierung nicht ganz. Zumindest nicht im Code.

Man fängt bei der 5 an und läuft rekursiv bis zur 1, also immer nach links. Danach gebe ich die 1 aus. Danach würde die 3 ausgegeben werden, sprich man klettert wieder hoch.

Ich verstehe nicht, wie das Hochklettern funktioniert. Weil nach der 1 würde man doch nach rechts springen wollen, was nicht geht, weil die 1 keine Kinder hat. Dasselbe nachdem ich die 1-3. und die 4 ausgegeben habe: Wie springe ich wieder hoch zur 5?

Also im Pseudocode verstehe ich das Prinzip schon. Immer links, Wurzel, rechts. Aber im richtigen Code nicht.

Ich habe diesen Codeabschnitt von ChatGPT:

def in_order_traversal(root):
  if root is not None:
    # Zuerst den linken Teilbaum durchlaufen
    in_order_traversal(root.left)

    # Dann den Wurzelknoten besuchen
    print(root.value)

    # Schließlich den rechten Teilbaum durchlaufen
    in_order_traversal(root.right)

...zur Frage

Wie löse ich diesen Python-Loop am besten?

Hallo,

in folgendem Loop, bei dem my_list eine Liste aus Objekten ist

for x in my_list:
  if x["key"] == 10:
    print("Tue etwas")

weiß ich, dass sobald x["key"] einmal 10 ist, alle folgenden Einträge auch 10 sein werden. Wie kann ich mir am elegantesten die darauffolgenden Abfragen sparen?
Ich hätte schon daran gedacht, einen Iterator mit dem next() keyword bis zu x["key"] = 10 springen zu lassen und danach ohne weitere Abfrage über die restlichen Listenelemente zu iterieren... weiß jemand, wie man das in Python möglichst elegant macht?

Danke und VG,

Nico

...zur Frage

Warum ist die Codefrage in der Theorie kein Algorithmus in python aber schon?

...zur Frage

wie funktioniert merge sort?

...zur Frage

Hilfe bei Python/Greedy Algorithmus?

Ich verstehe nach mehrmaligem Herumprobieren leider nicht wieso meine Ausgabe von der Erwarteten abweicht. Hier mein bisheriger Code:

und hier die Testfälle:

sowie meine Ausgabe:

testExample_1: (8,47)

testExample_2: (8,435)

testExample_3: (3,9)

Ich würde mich über jegliche Hilfe freuen :)

...zur Frage

Roulette Algorithmus

Guten Tag zusammen,

ich sags schonmal vorweg: Klar, es gab schon die ein oder andere Frage über Algorithmen im Roulette. Da es ein paar Fragen mehr sind, verfasse ich das alles mal in einem Thread.

1.)Gibt es ein Programm, das Algorithmen vom Roulette errechnen kann und wenn ja, welches ist zu empfehlen?

Gehen wir mal von folgender Situation aus: Ich schreibe mir z.B. die letzten 12 gefallenen Zahlen auf. Diese gebe ich dann in mein Programm ein. Der Computer berechnet dann den Algorithmus und ich hab die nächsten fallenden Zahlen.

2.) Kommen die errechneten Zahlen dann auch vor?

Ich meine, der Roulette-Automat generiert die Zahlen ja nicht jedes mal nach Zufall, sondern nach einem bestimmten Algorithmus. Und der kann sich dann ja nicht von meinem Programm und dem Roulette-Automaten unterscheiden oder?

3.) Darf sich ein Roulette-Automat auch "umentscheiden"?

Mir ist neulich ein "Phänomen" aufgefallen, wohlmöglich aber auch eigenes Pech^^ Ich habe eine ganze Zeit mit niedrigem Einsatz "1 Euro" immer richtig getippt. Doch sobald ich den Einsatz in die Höhe ziehe "5 oder 10 Euro" kommt immer genau das Gegenteil. Als wenn der Automat so darauf programmiert ist, ab einem bestimmten Betrag was anderes auszugeben. Wobei das ja dann Betrug wäre und Automaten notariell beglaubigt werden müssen.

Ich bin mir sicher, dass ich mir das alles viel zu einfach vorstelle, da wären dann bestimmt schon mehrere Leute drauf gekommen. Trotzdem interessieren mich dazu mal andere Meinungen.

Mit freundlichem Gruß

Sibi90

...zur Frage

Python Programmierumgebung Anaconda oder Visual Studio?

Hallo zusammen :)

Ich möchte die Programmiersprache Python lernen, bin aber noch Programmieranfänger. Kann bisher nur etwas Java. Java habe ich bisher immer in Eclipse programmiert. Nun suche ich für Python eine andere Programmierumgebung, ich glaube das nennt sich dann IDE. Ich dachte da zuerst an Visual Studio, weil man da auch mehrere Sprachen progammieren kann und das ja ganz nützlich sein kann, wenn man noch Sachen wie C++ oder JavaScript lernen möchte. Jedoch gibt es ja auch Anaconda für Python. Das verwirrt mich etwas. Ist Anaconda jetzt eine IDE für Python direkt oder lässt sich damit auch weiteres programmieren?

Irgendwo habe ich auch mal gesehen, dass eine Art Visual Studio Code in Anaconde mit enthalten ist. Ist das jetzt das Gleiche wie das normale Visual Studio oder gibt es da Unterschiede? Außerdem gibt es im Startbildschirm von Anaconda noch mehrere Sachen wie Spyder oder Jupyter oder sowas. Was ist das denn genau? Ich versuche mich da einzulesen aber momentan verwirrt mich das alles mehr als es mich weiter bringt. Ich würde mich riesig freuen, wenn mir jemand mal erklären kann, was es mit den ganzen Einzelheiten aus sich hat.

Wenn Visual Studio und Anaconde im Groben das Gleiche sind, was würdet ihr mir dann eher empfehlen?

Ich hoffe ihr könnte meine Verwirrung etwas auflösen :D Wäre euch wirklich dankbar für jede Hilfe.

Mit freundlichen Grüßen

...zur Frage

Java Schleife?

Schreibe eine Methode, die ...

ein Array von 10 ganzen Zahlen erzeugt und dieses mit den Werten 0², 1², 2², ... belegt und ...danach die Zahlen von 9² bis 0² ausgibt

Hätte man nach dem "einfachen code" also quasi bei aufgabe 2 auch folgendes hinschreiben können:

For (i=9; i>zahlen.lenght; i--)

...zur Frage

Anzahl Algorithmus-Operationen bestimmen?

Hallo an alle,

anbei (in Blau) die Aufgabe, dann das dazu benötigte Struktogramm und die Lösung. Es wäre nett, wenn mir jemand erklären könnte, wie ich diese Lösung zu verstehen habe, erschließt sich mir leider nicht (Bin neu in der Informatik).

...zur Frage

Wie führt man dieses Programm aus? Wie bekomme ich es? Github, Python, Programmierung?

Hei, ich halte in Schulprojekt über Dijkstras Algorithmus und würde gerne dieses Programm der Klasse vorführen, doch wie bekomme ich es und wie führe ich es aus? LG xd

Programm: https://github.com/raphsenn/Python-Pathfinder-with-Dijkstras-Algorithm

...zur Frage

Chudnovsky Algorithmus in C?

Ich versuche gerade den Chudnovsky Algorithmus in C zu implementieren um die nachkommastellen von Pi zu rechnen. Jedoch sind die häufigsten Ergebnisse immer nan, -nan, inf oder was wie 3.827783e-647. Ich hab auch verschiene print formate verwendet um das ergebnis auszugeben, aber da kam entweder 0.0000 oder inf raus.

Wie bekomm ich es hin das eine 'normale' Zahl rauskommt, quasi 3.14159...... usw.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

long double fact(long double n) {
  long double fac = 1.00;
  for (int i = 1; i<=n; i++) {
    if (i) {
      fac = fac * i;
    }
  }
  return fac;
}


int main(int argc, char* argv[]) {

  long double n, i;
  long double sum, pi, term;
  sum = 0.00;
  pi = 0.00;

  n = (atoi(argv[1]));

  for (i=0; i < n; i++) {
    term = (powl((-1.00), n) * fact(6.00*n) * (545140134.00*n + 13591409)) / (fact(3.00*n) * powl(fact(n), 3.00) * powl(640320.00, 3*n+3/2));

    sum += term;
  }
  sum = sum * 12;

  pi = 1 / sum;


  printf("PI: %Lf\n", pi);
  

  return 0;
}

...zur Frage

Flussdiagramm zu Sieb des Eratosthenes, Algorithmus?

Kann jemand zu dem struktogramm ein Flussdiagramm erstellen/zeichnen?

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen