Aus Algorithmus (Code) die Komplexitätsklasse ableiten?

Hallo,

wenn ich einen Code wie folgenden hab, zähle ich dann einfach die Anzahl der Operationen und setze sie ins Verhältnis mit der Elementanzahl? Ist das berechnen einer Variable wie "middle" gleichwertig mit einem Vergleich (O(1))? Im Falle des ersten, großen Feldes wird der Algorithmus bis zum Ergebnis insg. 6 mal aufgerufen und hat je 2 Vergleiche und ein mal middle berechnen. D.h bei 20 Elementen 18 (mit Variable berechnen) bzw 12 (nur die Vergleiche) Operationen. Aber wie man ab da weitermacht, weiss ich nicht. Wäre die Komplexitätsklasse in dem Fall dann (O(n))?

Danke für eure Hilfe

Bild zum Beitrag

1 Antwort

KarlRanseierIII

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

programmieren, Algorithmus

09.02.2023, 14:57

O(log(n)). Du kannst natürlich das Mastertheorem auspacken, aber im Endeffekt bestimmst Du den mittleren Index als middle, und wählst dann anhand eines Vergleiches entweder den oberen oder den unteren Teil.

Ich möchte nun einen Taschenrechner in Python programmieren, bei dem man mehrere Operationen durchführen kann. Beispiel: "4*5+5".

Ich habe aber schon die ersten Probleme bei der Aufgabe, die einzelnen Operatoren zu extrahieren und dann mit dem restlichen Eingabestring weiterzumachen.

ex = "4*5+5"

p = [] #Variable für Zahlen
op = [] #Variable für Operationen
op_counter = -1 #Variable um Operationen zu zählen

for x in ex:
  if x.isdigit() == False:
    op_counter += 1
    op[op_counter] = x

Das wäre meine erste Idee wie ich die Operanten rausextrahiere. Leider weiß ich nicht wie ich weiter machen soll. Ich denke dieser Weg ist etwas zu kompliziert.

Hier mein einfacher Taschenrechner:

https://www.gutefrage.net/frage/was-wuerdet-ihr-an-diesem-python-code-verbessern

ps: Tipps bitte mit Codebeispielen

...zur Frage

C Code funktioniert nicht?

Hallo,

Ich lerne gerade C.

Warum funktioniert dieser Code nicht?

Das Programm soll je nach Eingabe von Fahrenheit nach Celsius oder umgekehrt umrechnen. Dafür wollte ich in eine Variable 'einheit' vom Datentyp 'char' die Einheit festlegen lassen und abhängig davon die Temperatur berechnen lassen. Aber das Programm ignoriert den entsprechenden scanf-Befehl. Warum?

...zur Frage

Java - Distanzmatrix Algorithmus, Wie ansetzen?

Hallo, ich bin gerade dabei ein Graphenprogramm zu schreiben und stecke bisschen bei der Distanzmatrix.

Ich weiß nicht ob sich jemand bei Graphentheorie auskennt oder nicht aber der Algorithmus für die Distanzmatrix ist relativ einfach. Nur das umsetzen in Code fällt mir sehr schwer und deswegen hoffe ich, dass ihr mir vielleicht dabei helfen könnt..

Der Algorithmus für eine Distanzmatrix lautet so:

Man hat eine Eingangsmatrix (Adjazentmatrix).
Die könnte so aussehen:

Man markiert sich alle Nuller die in der Adjazentmatrix vorkommen (AUßER DIE HAUPTDIAGONALE, DIE BLEIBT UNBERÜHRT).

Dann erstellt man sich eine eigene Matrix die man "DistanzMatrix" nennen kann und setzt alle Nuller die eben in der Adjazentmatrix vorkommen auf "Unendlich" oder auch auf INTEGER.MAX_VALUE in der Programmiersprache .

Das schaut dann so aus:

Also haben wir jetzt 2 Matrizen. Bis dahin habe ich es auch geschafft in meinem Programm. Die Ausgabe schaut bei mir so aus:

Die "-9" sind alle Nuller, die auf UNENDLICH gesetzt sind (siehe zweites Bild).

Der nächste Schritt ist es die Potenzen der Eingangsmatrix (Adjazentmatrix) zu berechnen. Das habe ich ebenfalls schon geschafft im Code.

Das heißt, die Adjazentmatrix (siehe Bild 1) wurde potenziert und so könnte das Ergebnis der Potenzberechnug aussehen.

Man schaut sich jetzt alle Nuller (außer die Hauptdiagonale von der Eingangsmatrix an (siehe Bild 1)) und markiert sich nur die Zahlen (rot), die sich von der Potenzierung der Eingangsmatrix verändert haben. (Außer die Nuller (=Neue Nuller die durch die Potenzierung entstanden sind bleiben auch weiterhin eine Null))

Und der letzte Schritt ist es jetzt, die von mir erstellte DistanzMatrix upzudaten, indem ich im ersten Schritt alle rote Zahlen von A²(G) in 2 umwandle. Alle Nuller die übrig bleiben, werden wieder in UNENDLICH umgewandelt.

Und das wird jetzt so oft wiederholt, bis es keine UNENDLICH Zeichen mehr in der Distanzmatrix gibt. Und aus UNENDLICH wird 3. Und immer so weiter.. Falls es zb nach der fünften Potenzierung immer noch Nuller bzw UNENDLICH Werte gibt dann wird aus UNENDLICH 5.

Somit ist D³(G) das Ergebnis.

Ich hoffe ich konnte es ausführlich genug erklären

Danke

...zur Frage

Algorithmus Ampelsteuerung?

Hallo Leute, ist meine Lösung richtig oder wie kann man diese Aufgabe lösen ?

...zur Frage

Ist ein B-Baum dasselbe wie ein (a, b)- Baum?

Wie in der Überschrift würde ich gerne wissen, ob ein B-Baum dasselbe ist wie ein (a, b) - Baum. Was mir aufgefallen ist, ist das diese sich sehr ähneln.

...zur Frage

O-Notation in der Mathematik?

Hallo, ich hab die O-Notation schon so mehr oder weniger verstanden, also dass es um den Zeit/Platzverbrauch von Algorithmen geht und bei O(n^3) der Zeit/Platzverbrauch immer hoch drei dem Eingegebenen entspricht.

Was ich aber nicht verstehe, wie man das bei mathematischen Ausdrücken zeigen soll. Z.B.:

Was ich mir vorstellen könnte wäre, dass n die Eingabe entspricht und der Funktionswert der dann rauskommt gleich der Eingabe hoch vier entsprechen muss (ist hier ja aber nicht der Fall).

...zur Frage

In Java bestimmte Werte aus einem Array in Indexvariable eines neuen Arrays speichern?

Hallo,

ich habe gerade das Problem, dass ich an einer Aufgabe sitze, bei welcher man ein Neues Feld erzeugen soll in welchem die Werte aus einem vorgegebenen Feld so eingefügt werden, dass alle negativen Zahlen im linken Bereich und alle postiven Zahlen sowie 0 im rechten Bereich liegen. Gegeben ist folgender Code:

public static int randomInt(int a, int e) {
    return (int) (Math.random() * ((e - a) + 1)) + a;
}

public static void fuellen(int[] feld, int a, int e) {
    for (int i=0;i<feld.length;i++){
        feld[i] = randomInt(a,e);
    }
}

public static void ausgeben(int[] feld){
    for (int i=0;i<feld.length;i++){
        System.out.printf("%3d ", feld[i]);
        if ((i+1) % 10 == 0) {
            System.out.println();
        }
    }
    System.out.println();
}

bis Jetzt war mein Ansatz dieser hier:

public static int[] verteilen(int[] feld){
    int[] feld2 = new int[feld.length];
    int first = feld2[0];
    int last = feld2[feld2.length - 1];
    int count = 0;
    int right = feld2.length - 1;
    for(int i=0;i<feld.length;i++) {
        if(feld[i] < 0) {
            first = feld[i];
            count++;
        }
        else {
            last = feld[i];
            right--;
        }
    }
    return feld2;
}

und als Ergebnis soll das rauskommen aber irgendwie klappt es nicht:

39-34 76-84-79-61-59-50 96 55 -71-51-89 77 64 93-20-86 43 33

-34 -84 -79 -61 -59 -50 -71 -51 -89 -20
-86  33  43  93  64  77  55  96  76  39

...zur Frage

Optimaler Suchbaum Eigenschaften prüfen?

Hallo, ich habe folgende Aufgabe:

Gegeben sei der folgende Suchbaum, in dem die Elemente A;B;C;D;E

lexikographisch geordnet sind. Beweisen oder widerlegen Sie:

Der Baum kann ein optimaler Suchbaum mit 2,1 erwarteten Vergleichen sein.

Da kommen ich und viele andere nicht weiter, die meisten neigen zur Meinung, dass die Aussage falsch ist. Wir haben dazu sehr viele Gleichungen aufgestellt, die aber kompliziert zu lösen scheinen: (a bis e sind die jew. Zugriffswahrscheinlichkeiten)

a+b+c+d+e=1

a+2b+4c+3d+4e=2,1

Durch die e_ij Tabellen (erwartete Anzahl Vergleiche im Unterbaum von i bis j):

b<=a, e<=d<=c

Aber ich stecke jetzt fest wie ich hier wirklich weiterkomme. Muss ich etwa noch mehr Ungleichungen/Gleichungen aufstellen?

Vielen Dank im Voraus!

...zur Frage

C++ alle Kombinationen eines Strings mit der Länge L mit zurücklegen?

Hallo,

ich möchte so etwas wie einen Password-List-Generator schreiben, komme aber nicht auf die richtige Rekursionsfunktion.

Es soll zum Beispiel aus einem Zeichensatz wie "abcdef" und der information L = 9 Passwörter im vector<string> zurückgegeben werden, bei denen jeder der Buchstaben an jeder Position 0, 1, .., 9 mal vorkommt, wie beim Passwortgenerator "crunch".

Hat mir jemand ein Code-Beispiel parat?

Viele Grüße

Lukas Z

...zur Frage

Kann mir jemand helfen?

Ich soll ein Struktogramm für diese Aufgabenstellung erstellen: Erstellen Sie einen Algorithmus, der den Benutzer nach zwei Zahlen Z1 und Z2 fragt und der anschließend ausgibt, ob

• Z1 größer als Z1 ist, oder

• Z1 kleiner als Z2 ist, oder

• beide Zahlen gleich sind.

Mein Struktogramm sieht so aus:

Bei der Auswertung im Programm bekomme ich immer Fehler und ich weiß nicht was an meinem Struktogramm falsch ist:

...zur Frage

Standardbildungsenthalpie von Wasser berechnen?

Für die Reaktion von Wasserstoff mit Ozon 3H2 (g) + O3 (g) → 3 H2O (g) wurde eine Reaktionsenthalpie von -868,1 kJ/mol gemessen. Berechne die Standardbildungsenthalpie für H2O (g) mit diesem Wert. (Standardbildungsenthalpie Ozon: +142,7 kJ/mol)
Die Standardbildungsenthalpie für Wasser aus den Elementen ist -241,8 kJ/mol. Vergleiche deinen Wert aus Aufgabe 1 mit diesem Wert und erkläre.

Hallo alle zusammen, ja ich weiß es sind Aufgaben zum Üben….

Dennoch wollte ich Fragen, ob einer mir eine perfekte Lösung hier für geben kann, damit ich die nächsten Aufgaben alleine lösen kann…

...zur Frage

Big O notation?

Wie löst man die obige Aufgabe. Habe mir jetzt ein paar Videos zum Thema angeschaut und kann ein paar Algorithmen analysieren. Bei obigem komme ich aber nicht weiter.

Beim ersten Algorithmus muss ich die Multiplikation ja jedes mal durchführen, während beim zweiten nur ein einziges mal am Ende multipliziert wird. Daher hätte ich gesagt:

Algorithmus O(n), da ich die Multiplikation jedes mal durchführen muss
Algorithmus O(1), da ich jedes mal aufsummieren muss und erst dann multipliziere.

Meine Fragen:

Ist die Analyse korrekt?
Das was ich da aufgeschrieben habe, ist ja nur ein intuitive Analyse auf Basis der Videos, die ich mir angeschaut habe. Wie wäre die formelle Herangehensweise, also wie kann ich das systematisch herausfinden?
Was ist nun der Unterschied zwischen Zeit-Komplexität T und Big O-Notation in der Aufgabenstellung.

...zur Frage

Hat jemand eine Idee wie man diese Informatik Hausaufgabe lösen könnte?

Das Marienkäfer namens Kara soll verschiedene Baumstämme mit Kleeblättern ausfüllen. Hierfür soll ich einen Algorithmus entwickeln aber ich habe keine Idee wie. Hat jemand vielleicht einen Plan? Die Aufgabe ist aus der 10. Klasse Informatik Grundkurs

...zur Frage

Welcher Sortieralgorithmus ist unter welchen Umständen der schnellste?

Nabend.

Da ich mich ja mit der Programmierung beschäftige, habe ich versucht, einige Sortieralgorithmen in C++ nachzuprogrammieren (und mir danach die schnelleren Versionen aus dem Netz raus zu suchen). Dann wollte ich anhand einer Liste von 500.000 Elementen testen, welcher Algorithmus der Schnellste ist.

Getestet habe ich bisher std::sort, Quick Sort, Insertion Sort und Timsort. std::sort war bei der unsortierten Liste zwei Millisekunden schneller als Timsort, danach folgte Insertion Sort und Quick Sort war letzter. Wenn ich aber ein neues Element zu der sortierten Liste hinzugefügt habe, war Timsort der schnellste Algorithmus mit sage und schreibe 0 Mikrosekunden. Danach folgten Insertion Sort, std::sort und zu guter letzt war mal wieder Quick Sort fertig.

Wenn ich das ganze kurz zusammenfassen sollte, würde ich sagen, dass Timsort an dieser Stelle der beste Sortieralgorithmus ist, auch wenn er zwei Millisekunden langsamer bei der Sortierung einer komplett unsortierten Liste als std::sort ist. Zwei Millisekunden sind vernachlässigbar, vor allem, wenn std::sort bei der Sortierung der bereits sortierten Liste mit einem neuen Element 9 Millisekunden braucht, während Timsort nicht mal eine Mikrosekunde benötigt.

Gibt es Sortieralgorithmen, die noch schneller sind als die vier vorhin genannten? Oder welche anderen Szenarien könnte ich testen?

Gruß

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen