Laufzeiten von Algorithmen?

Verstehe ich das richtig, wenn ich z. B. ein Array mit 8 Elementen habe, z. B.

11, 25, 33, 42, 54, 58, 67, 96, und jetzt wissen will, wie viele Vergleiche die Binäre Suche braucht, um das Element 11 zu finden, kann ich dann einfach die Komplexitätsklasse zu Hilfe nehmen? Also hier O(log n) und da es 8 Elemente sind, brauche ich hier 3 Vergleiche, da O(log2(8)) = 3 ist? In dem Fall haut es doch hin, da es bei der Suche der 11 nicht um den Best Case O(1) handelt, weil die 11 nicht in der Mitte steht.

Falls das richtig ist, klappt das immer? Also bei anderen Algorithmen auch, zumindest wenn ich den Fall (Best, Worst und Average) erkenne und dann die entsprechende Komplexität nutze?

1 Antwort

Vom Beitragsersteller als hilfreich ausgezeichnet

Seliba

18.06.2024, 17:41

Nein, das klappt nicht immer. Komplexitätsklassen beschreiben das Laufzeitverhalten von Algorithmen nur grob für große Eingaben, sind also nicht akkurat, weil kleinere Faktoren entfallen.

Ein Algorithmus mit 3*n + log(n) + 5 Schritten wäre beispielsweise in der Komplexitätsklasse O(n), braucht aber offensichtlich mehr als n Schritte.

Woher ich das weiß:Studium / Ausbildung – Informatikstudent

kabik334

Beitragsersteller

18.06.2024, 17:51

kappt meine aussage zumindest bei Binäre,linare suche sowie den einfachen suchalgos(z.b bubble,selection)? Für die Klausur reicht mir das :D

Seliba

18.06.2024, 17:59

@kabik334

Nein, funktioniert nicht. Bubble Sort zum Beispiel ist im worst case O(n^2), braucht aber nur n^2 - n Schritte. Ich glaube nicht, dass du die konkrete Anzahl von Schritten angeben musst, und wenn doch, vermutlich in Verbindung mit einem kompletten Sortiervorgang des Algorithmus. Wenn du den auf dem Papier ausführst, solltest du die Anzahl der Schritte einfach ablesen können :)

kabik334

Beitragsersteller

18.06.2024, 18:06

@Seliba

vielleicht hab ich mit den sortieralgos zu weit gegriffen, bis jetzt gabs es immer eine aufgabe wo ich lineare und binäre suche vergleichen musst und angeben musste wie viele vergleiche bzw iterationen gebraucht werden im ein element zu finden. lineare suche ist klar ,bei binär bin ich gerade unsicher. Die anzahl der verleiche ergibt sich doch dadruch wie oft ich mein array teilen muss oder?

Seliba

18.06.2024, 18:23

@kabik334

Ja, schon mehr oder weniger. Bestenfalls eben einmal, schlimmstenfalls log2(n) + 1 (aufgerundet) mal, aber alles was da nicht reinfällt muss man eben manuell nachrrechnen weil es von den konkreten Elementen abhängt. Die Komplexitätsklassen helfen dir bei sowas wirklich nicht.

Ähnliche Beiträge

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

...zum Beitrag

Warum sollte man Lineare Listen (arrays) als Datenstruktur verwenden?

Lineare Listen haben erstmal sehr viele Nachteile...

Die Datenstruktur ist nicht dynamisch (schwer zu erweitern)
Das Suchen in Arrays ist nur schwer in O(log(n)) möglich, da die binäre Suche sehr viel extraspeicher benötigt, und Sprungsuchen / Interpolationssuchen häufig nicht in O(log(n)) funktionieren
Sortierverfahren sind oftmals problematisch, da quicksort ggf. eine schlechte Worst-Case Komplexität hat.
Alle Elemente müssen nebeneinander im Speicher liegen, d.h. es gibt ein Limit wie groß ich ein Array machen kann.

Dagegen sind Bäume:

Dynamisch (sehr einfach zu erweitern, da man einfach nur Pointer hinzufügen muss)
Suche funktioniert aufbaubedingt IMMER in O(log(n))
Mit heapsort lässt sich immer im Worst-Case in O(n*log(n)) sortieren
Die Datenstruktur kann beliebig groß werden (man muss nur Pointer hinzufügen).

Meine Frage also, warum sollte man lineare Listen verwenden, und Warum lernt man x verschiedene Sortierverfahren von Insertion, Selection, Merge, Bubble & Quicksort für lineare Listen, wenn die einfachste Lösung ist einfach Bäume zu verwenden?

...zum Beitrag

Wie kann man Liste in Java sortieren?

Hey,

Ich muss eine Liste sortieren, die 15 Zahlen speichert. Am Ende sollen die Zahlen von klein nach groß geordnet sein.

Wie kann ich das machen?

Würde mich sehr über Hilfe freuen.

Liebe Grüße

...zum Beitrag

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

...zum Beitrag

ASCII Art in der Konsole ausgeben [C#]?

Guten Abend! Ich versuche seit einigen Tagen ein byte array in der Konsole auszugeben, was dann später "C#" als kleines Artwork in der Konsole ausgegeben wird. Ich weiß aber nicht, wie ich

a) mein Ganzes byte Array ausgeben lasse (er gibt nicht das vollständige array in der Konsole aus warum auch immer) und:

b) wie ich die Zahlen im array zu Zeichen zuweisen kann (sprich Leerzeichen, C und #) damit es das C# "artwork" in der cmd zeigt.

Wo liegen meine Fehler? Wenn möglich bitte mit Beispielen.

using System;
using System.IO;

namespace ESA_2
{
   class Program
   {
       public void ESAIn(string Path)
       {
           byte[] array = { 32, 32, 67, 67, 32, 32, 32, 35, 32, 35, 32,
                           32, 67, 32, 32, 67, 32, 32, 35, 32, 35, 32,
                           67, 32, 32, 32, 32, 32, 35, 35, 35, 35, 35,
                           67, 32, 32, 32, 32, 32, 32, 35, 32, 35, 32,
                           67, 32, 32, 32, 32, 32, 35, 35, 35, 35, 35,
                           32, 67, 32, 32, 67, 32, 32, 35, 32, 35, 32,
                           32, 32, 67, 67, 32, 32, 32, 35, 32, 35, 32 };

           //Anhand der ASCII Code Tabelle lassen sich 32 zu Leerzeichen, 67 zu C
           // und die 35 zu # Zeichen Übersetzen, was, wenn wir die Ausgabe
           //umstrukturieren, eine 'C#' in der Konsole ausgibt


           FileStream stream = File.Open(Path, FileMode.Truncate, FileAccess.ReadWrite);


           stream.Write(array, 0, array.Length);
           stream.Close();
       }
       public void ESAOut(string Path)
       {
           BinaryReader reader = new BinaryReader(File.Open(Path, FileMode.Open));
           var count = 0;
           for (int i = 0; i < reader.ReadByte(); i++)
           {
               count++;
               Console.Write("{0} ", reader.ReadByte());
               if (count == 11)
               {
                   Console.Write("\n");
                   count = 0;
               }
           }
           reader.Close();
           Console.WriteLine();
       }
       static void Main(string[] args)
       {
           string Path = @"C:\Users\Dean Aleksander\source\repos\ESA_2\ESA_2\ESA02.txt"; ;
           Program test = new Program();
           test.ESAIn(Path);
           test.ESAOut(Path);
           Console.ReadLine();
       }
   }
}

Die Aufgabenstellung: "Schreiben Sie eine Methode „ESA2In“ in einem neuen Projekt „ESA_2“, mit der dieses Array in eine in Ihrem Projektmappenordner anzulegende Datei „ESA2.txt“ gespeichert werden kann. Schreiben Sie sodann eine weitere Methode „ESA2Out“, mit der dieses Array aus der Datei ausgelesen und auf Konsole ausgegeben werden kann. Die Konsolenausgabe soll in sieben Zeilen mit jeweils elf Zeichen gegliedert werden – dies entspricht auch der vorstehenden Anordnung der Array-Elemente. Beachten Sie aber, dass eine Zeile im Array aus 33 Zeichen besteht – Ihre Konsolenausgabe soll hingegen elf Zeichen umfassen. "

...zum Beitrag

Deterministischer vs determinierter Algorithmus?

Hey Leute,

wie schon in der Überschrift erkennbar, verstehe ich diese zwei Arten von Algorithmen nicht ganz? Besonders was der Unterschied sein soll?

Vielen Dank,

Lyn

...zum Beitrag

Logarithmische Sortieralgorythmen?

Hallo,

ich habe vor kurzen über die O Notation eines Algorithmus gelernt und da gibt es die O Notation O(log(n)) und da habe ich mich gefragt welche Sortieralgorythmen haben diese O Notation. Nach Recherche habe ich leider nichts gefunden. Kann mir da wer weiterhelfen?

...zum Beitrag

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).

...zum Beitrag

Warum hat insertionsort keine lineare Laufzeit und eine Laufzeit von n*logn?

Dieser Algorithmus läuft ja immer linear, warum insertionsort nicht, der ja auch eigentlich nur Vergleiche vollzieht?:

Lösung n-1 vergleiche überall,

...zum Beitrag

Finde die zwei kleinsten Elemente mit 1,5n - 2 Vergleichen?

Hallo allerseits,

heute habe ich in meiner Berufsschule die Aufgabe bekommen, in einem Array / Liste die zwei kleinsten Zahlen zu finden mit maximal 1,5n - 2 Vergleichen.
Mein erster Gedanke war, ein Sortieralgorithmus drüber laufen zu lassen und dann einfach die ersten beiden Elemente zu returnen. Das Problem ist, dass mir kein Algorithmus mit nur 1,5n -2 Vergleichen einfällt und ich keine andere effiziente Lösung finde.

Hat jemand eventuell eine gute Lösung? Gerne iterativ und rekursiv.

Danke!

...zum Beitrag

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:

...zum Beitrag

Array erweitern in C?

Hallo.

Als Teil einer Methode in C zur Bestimmung, ob eine Zahl n eine perfekte Zahl ist (Summe aller echten Teiler von n ergibt n) will ich ein Array mit allen Teilern erstellen, welches dynamisch erweitert werden soll, bis alle Teiler enthalten sind. Danach soll man bestimmen können, dass die Zahl perfekt ist, wenn die Summe der Elemente n ergibt, und wenn nicht, dann nicht.

Wie kann ich das Array erweitern? Laut meinen Notizen kann man ein bestimmtes Element hinzufügen durch folgende Form (Beispiel): int array[] = { [7] = 42 } – dem achten Element wird der Wert 42 zugewiesen.

Hier mein bisheriges Programm. Der Wert von divisor soll als Element dem Array divisors[] hinzugefügt werden, wenn es sich um einen echten Teiler handelt, und zwar bis einschließlich der 1:

#include <stdio.h>
int main()
{
  int n,m,divisor,divisors[m];
  m = 0;
  printf("Geben Sie eine ganze Zahl ein.\n");
  scanf("%d",&n);
  for (divisor = n; divisor > 0;) {
    if (n % divisor == 0) {
      m++;
      divisors[m] = {[m] = divisor};
    }
    divisor--;
  }
  return 0;
}

Da meckert der aber rum:

main.c:11:27: error: expected expression before '{' token

Wie muss ich das schreiben, damit es funktioniert?

...zum Beitrag

Ein Kochbuch als Algorithmus?

Ich hab mal so eine Frage bzgl. Algorithmen und Datenstrukturen. In unserer Übung sollen wir beurteilen, ob ein Kochbuch ein Algorithmus wäre und dabei bin ich während einer Recherche ins grübeln gekommen.

Erstmal ist natürlich klar, dass ein Algorithmus eine endliche Abfolge von genau definierten Anweisungen zur Behebung eines Problems ist. Nun muss man bei einem Kochbuch bedenken, dass Anweisungen wie "Eine Prise Salz" nicht genau definiert sind und auch bei der Durchführung es unterschiedliche Resultate geben würde, z.B auf Grund verschiedener Backöfen, Kochtöpfe etc. was der Definition eines Algorithmus widersprechen würde. Wenn man wiederum die Umgebung digital simulieren würde, wäre das Resultat immer identisch.

Daher wollte ich euch mal fragen, wie ihr darüber denkt und ob ein Kochbuch ein Algorithmus wäre oder nicht

...zum Beitrag

Regulärer Ausdruck zu NFA/NEA?

Kann mir bitte Jemand weiterhelfen, diesen NFA/NEA zu konstruieren?

Mit "alle drei" Automaten sind jeweils der Automat von [0-9], [0-9]* und [0-9][0-9]* gemeint.

Für [0-9] habe ich den Automaten:

-->(q0)----[0-9]---->((q2))

Für die restlichen beiden habe ich auch eine Lösung, jedoch wurde mir gesagt, dass wir Epsilon bzw. Lambda nicht benutzen dürfen.

Ich verstehe jedoch nicht wie ich dann 5 Zustände und 6 Kanten erreichen soll beim finalen Automat.

...zum Beitrag

Was möchtest Du wissen?

Deinen Beitrag erstellen