Laufzeit einer sequentiellen- bzw. binären-Suche berechnen.
-
Mechanics schrieb:
Achso, Festplatte, nicht Diskette. Wow, sowas kennt dein Prof also schon.
Ja doch. Ist einer der Professoren die nicht in den 80er stehen geblieben sind.
Mechanics schrieb:
Ansonsten, was ist dir nicht klar? Wie viele Operationen brauchst du, um einen Eintrag binär/sequentiell zu finden?
Unter'm Strich ja, wie komme ich auf die Anzahl der Operationen? Für den konkreten Fall hier konnte ich es mithilfe eines Kommilitonen lösen, aber das dahintersteckende Prinzip ist mir nicht klar.
-
Die Komplexitätsklassen sind bekannt. Lineare Suche ist O(n) und Binärsuche ist O(log(n)). Das muss man wissen, das sind Grundlagen.
Wie man das selber herleitet (z.B. für neue Algorithmen) ist natürlich grundsätzlich nicht so trivial, aber in dem Fall wärs auch trivial, das selber herzuleiten.
-
Mechanics schrieb:
Die Komplexitätsklassen sind bekannt. Lineare Suche ist O(n) und Binärsuche ist O(log(n)). Das muss man wissen, das sind Grundlagen.
Vollkommen klar.
Um mal bei meiner ursprünglichen Aufgabe zu bleiben.
Mein naiver Denkansatz wäre doch, ich habe 500.000 Einträge in meiner Indexdatei, welche ich durchsuchen muss. Sprich 500.000 Suchoperationen...
Tatsächlich wird das hier aber laut Kommilitione so berechnet.
(500000 * (28+4))/512
Somit komme ich auf 31250 Operationen
Nur warum?Warum muss ich überhaupt die Länge des Schlüssels (28 Zeichen) und die Länge des Adressverweis (4 Zeichen) addieren?
-
Ich hätt gesagt +4, nicht *4. Ich find die Aufgabe jetzt aber nicht interessant genug, um da was reinzuinterpretieren.
Die Frage ist, wie viele Daten du lesen musst. Und da du Informationen über die Zugriffszeiten auf Sektoren hast, interessiert dich, wieviele Sektoren du lesen musst. Die Angaben hätt ich jetzt so interpretiert, dass der Key im Index 28 Byte groß ist, der Verweis auf den Datensatz 4, also insgesamt 32 Byte pro Eintrag im Index. Das multiplizierst mit der Anzahl der Einträge und dividierst durch die Größe eines Sektors, dann weißt du, wieviele Sektoren du lesen musst, und kannst die Zeit ausrechnen.
Und wenn du eine Binärsuche machst, dann musst du keine 500 000 Einträge anschauen, sondern etwa 20, und entsprechend dann nur 20 Sektoren lesen.Eigentlich ist die Aufgabe völlig sinnlos. Macht man das echt in einem Studium?
-
Mechanics schrieb:
Ich hätt gesagt +4, nicht *4. Ich find die Aufgabe jetzt aber nicht interessant genug, um da was reinzuinterpretieren.
Die Frage ist, wie viele Daten du lesen musst. Und da du Informationen über die Zugriffszeiten auf Sektoren hast, interessiert dich, wieviele Sektoren du lesen musst. Die Angaben hätt ich jetzt so interpretiert, dass der Key im Index 28 Byte groß ist, der Verweis auf den Datensatz 4, also insgesamt 32 Byte pro Eintrag im Index. Das multiplizierst mit der Anzahl der Einträge und dividierst durch die Größe eines Sektors, dann weißt du, wieviele Sektoren du lesen musst, und kannst die Zeit ausrechnen.
Und wenn du eine Binärsuche machst, dann musst du keine 500 000 Einträge anschauen, sondern etwa 20, und entsprechend dann nur 20 Sektoren lesen.Eigentlich ist die Aufgabe völlig sinnlos. Macht man das echt in einem Studium?
OK, das hilft mir schon mal weiter.
Eigentlich ist die Aufgabe völlig sinnlos. Macht man das echt in einem Studium?
Ja, Wirtschaftsinformatik, 1.Semester, Theoretische Grundlagen, Graphentheorie.
Das Studium ist sowieso total speziell. Alles so furchbart Wirtschafts-orientiert. Von den Mathematik-Vorlesungen will ich gar nicht erst anfangen...
Aber warscheinlich bekomme ich für das Sommersemester ne Zulassung für ein richtiges Informatikstudium
-
Ich habe in Foren mehrfach gelesen das man den Bug bei AMD 'aktivieren' muss, damit es funktioniert.
Kann mir jemand erklären was das bedeuten soll?Ich habe einen AMD Phenom und will bald was neues kaufen, die Preise gehen schon runter. Aber vielleicht werden ja bald neue Prozessoren auf den Markt kommen.
-
! Ups, sorry, bitte löschen, war für einen anderen Thread !
-
@axels Hast du zu der Aufgabe eine Lösung gefunden?
Habe momentan im Studium die gleiche Frage und finde keine Richtige Antwort.Würde dir gerne Privat schreiben, habe mich aber gerade erst hier angemeldet und darf das anscheinend noch nicht, da ich nicht über ausreichende Berechtigung verfüge.
-
@OlliWif sagte in Laufzeit einer sequentiellen- bzw. binären-Suche berechnen.:
habe mich aber gerade erst hier angemeldet und darf das anscheinend noch nicht
Das hat nichts mit Berechtigungen zu tun. Es gibt hier keinen Chat für "Normale" User. Discord: https://discord.gg/EPFvDHh
& bitte grab in Zukunft keie Uralt-Threads mehr aus. Wenn du eine Frage hast, mach' bitte einen neuen Thread auf.
-
@Swordfish Schade um den Chat, habe bloß die Vermutung, dass @axels und ich an der gleichen Hochschule studieren könnten. In meinem Studium kam die gleiche Frage ebenfalls in Theoretischen Grundlagen vor und meine Mathematik Vorlesung ist ebenfalls nicht der Hit. Und falls wir an der gleichen Hochschule studieren, wollte ich einfach paar Tipps für die kommende Prüfungsphase aufschnappen.
-
@OlliWif Ich war zu der Zeit, als ich den Thread erstellt habe, an der HS Ansbach. Bin dort aber schon seit einem Jahr nicht mehr...
Sollte jetzt auch genug Off-topic sein für so einen alten Thread.
-
@axels Tut mir echt Leid, dass ich nochmal schreibe, aber ich studiere ebenfalls an der HS Ansbach Wif. Hast du eventuell ein paar Tipps für mich für die kommenden Prüfungen? Vor allem eventuell für GDI und Programmieren?
Bin momentan im ersten Semester und habe jetzt die ersten Prüfungen vor mir.
-
@OlliWif Komm auf den Discord https://discord.gg/EPFvDHh vom Forum, da ist der richtige Platz für Off-topic
