Frage nach Effizienz



  • @SeppJ sagte in Frage nach Effizienz:

    Das ist sicher richtig, aber nicht im Sinne der Aufgabenstellung.

    Who00t? Also nichts in den Bodies ist schlimmer als O(n²) also darf ich es wohl getrost ignorieren!?
    Naja, dann sage ich daß die Komplexität der Loop-bodies die nicht selbst Loops sind unter der Komplexität des Gesamtalgorithmus liegen und somit ignoriert werden können. *strike*

    @SeppJ sagte in Frage nach Effizienz:

    wo es hier doch um theoretische Informatik und nicht um Compileroptimierung geht.

    ich habe keine Ahnung von theoretischer Informatik. Was ist das? ^^

    Ich habe nur festgestellt, daß nichts davon von der Eingabegröße abhängt. Und irgendwelche Additionen, Multiplikationen auf doubles sind O(1). Ich weiß nicht, gibt es dafür einen Namen? Ich würde sagen "Atomics".

    @SeppJ sagte in Frage nach Effizienz:

    Man will ja beurteilen, welche Effizienzklasse der Algorithmus bzw. dieses Schleifenmuster hat.

    Naja, O(n²).


  • Mod

    @Swordfish sagte in Frage nach Effizienz:

    ich habe keine Ahnung von theoretischer Informatik. Was ist das? ^^

    Ich habe nur festgestellt, daß nichts davon von der Eingabegröße abhängt. Und irgendwelche Additionen, Multiplikationen auf doubles sind O(1). Ich weiß nicht, gibt es dafür einen Namen? Ich würde sagen "Atomics".

    Völlig daneben. Ich bin mir nicht sicher, ob du den Kommentar zu deiner Ahnung von theoretischer Informatik ironisch gemeint hast. Falls nicht: Das lernst du dann da, was hier gemeint ist. So etwa erste Vorlesung, erstes Semester. Wobei ich das Thema schon im Informatikunterricht in der Oberstufe hatte.



  • @SeppJ sagte in Frage nach Effizienz:

    Völlig daneben.

    Care to elaborate? Ok, O(1) bezogen auf gängige Rechnerarchitekturen ^^

    @SeppJ sagte in Frage nach Effizienz:

    So etwa erste Vorlesung, erstes Semester.

    Du solltest eigentlich inzwischen längst wissen, daß ich ein ungebildeter dahergelaufener bin.



  • @SeppJ sagte in Frage nach Effizienz:

    @Finnegan sagte in Frage nach Effizienz:

    Angenommen, ich habe einen Algorithmus, der ein Problem der Größe n in nSchritten löst (O(n)), aber in jedem Schritt ein Buchhaltungs-Array mit 100 Elementen sortieren muss, dessen Größe konstant und unabhängig von der Problemgröße ist. Egal welchen Sortieralgorithmus ich dafür verwende, fließt dieser Sortiervorgang bei der Komplexitätsbetrachtung mit konstanter Laufzeit ein. Ob Quicksort oder Bubblesort, mein (äußerer) Algorithmus bleibt O(n).

    Nein?! Dein Algorithmus hat einen konstanten Teil und einen linearen Teil. Das gilt aber insgesamt immer noch als O(n), egal wie groß die Konstante ist. Die O-Notation ist keine strikte Formel, wie viel Laufzeit ein Algorithmus genau für welches N braucht, sondern eine asymptotische obere Grenze. Denn diese ist es, die beim Vergleich von Algorithmen in erster Linie interessant ist.

    Sehr richtig. Ich dachte eigentlich, dass ich nichts widersprechendes geschrieben hätte (?). Der "Gag", wie ich ihn meinte, war dass dieser Algorithmus:

    löse_praktisches_problem(problem):
        wenn problemgrösse(problem) >= 2^64 dann
            return
        sonst
            return löse_problem_mit_gängigem_algorithmus(problem)
    

    gemäß mathematischer Definition in O(1) liegt (Anzahl der Rechenschritte ist stückweise Folge, die ab dem 2^64-ten Glied, und somit auch ihr Limes superior 1 wird). Aber auch wenn die meisten konkreten Implementierungen von Algorithmen so wie oben aussehen - interessant ist natürlich die Laufzeit des allgemeinen (inneren) Algorithmus (der äußere ist eine andere Fragestellung).

    Wenn bis jetzt noch keiner schmunzeln musste, dann gebe ich jetzt auch endlich Ruhe 😉



  • @Finnegan sagte in Frage nach Effizienz:

    Wenn bis jetzt noch keiner schmunzeln musste

    Wenn Du mich kitzelst vielleicht.


  • Mod

    @Swordfish sagte in Frage nach Effizienz:

    @SeppJ sagte in Frage nach Effizienz:

    Völlig daneben.

    Care to elaborate? Ok, O(1) bezogen auf gängige Rechnerarchitekturen ^^

    Du bist halt total am Thema vorbei mit allem was von Rechnerarchitekturen, Optimizern, doubles, und sonstiger Technik zu tun hat. Das hier hat absolut gar nichts mit technischer Umsetzung zu tun. Das hier ist Mathematik, nicht rechnen mit dem Taschenrechner.



  • @Finnegan sagte in Frage nach Effizienz:

    Wenn bis jetzt noch keiner schmunzeln musste, dann gebe ich jetzt auch endlich Ruhe

    Ich fand's lustig!



  • @SeppJ Ähm. Es geht doch um die komplexität von dem gesamten Dingsti? Da ist es doch ziemlich egal wenn irgendetwas darin < O(n²) ist?


  • Mod

    @Swordfish sagte in Frage nach Effizienz:

    @SeppJ Ähm. Es geht doch um die komplexität von dem gesamten Dingsti? Da ist es doch ziemlich egal wenn irgendetwas darin < O(n²) ist?

    Ich verstehe nicht, wie sich das auf meine Antwort bezieht.



  • Ich verstehe nicht, wie sich Deine Antwort auf meine Frage

    @Swordfish sagte in Frage nach Effizienz:

    Care to elaborate?

    bezieht. Ein paar mehr Worte bitte.


Anmelden zum Antworten