Frage nach Effizienz



  • Hallo zusammen , ich habe eine Frage nach Effizienz und zwar , Wie kann man z.b diese

    double s = 0;
    
    for (int i= 0 ; i < 10 ; i++){
    s++;
    
    for (int k= 1 ;k < n; k+=2){
    s= s * k;
    s--;
    
    for (int j = n ; j > n/2 ; j--){
    s = (s + j) / 2;
    }
    }
    for (int 1= 1 ; 1<= n ; 1++){
    s*= 2;
    }
    }
    

    Wie kann man kennen die Anzahl der Aufrufen kennen ? , Wie wird der Ausdruck mit Landau-Notation berechnet ?, es wäre nett von euch , wenn jemand mir das erklären kann , weil ich keine Ahnung habe .



  • @Haggard sagte in Frage nach Effizienz:

    for (int 1= 1 ; 1<= n ; 1++){
    

    Spätestens jetzt weißt Du warum Bezeichner mit nur einem Zeichen (insbesondere l) kacke suboptimal sind. i und j oder n und mnah beieinander sind auch so Klassiker zum Abgewöhnen.

    int n;
    
    for (int i = 0; i < 10; i++) {  // konstantes Laufzeitverhalten
    
    	for (int k = 1; k < n; k += 2);  // n/2
    		for (int j = n; j > n / 2; j--);  // n/2
    
    	for (int k = 1; k <= n; k++);  // n
    }
    

    O((n/2)² + n) würde ich sagen was Element von O(n²) ist, also quadratische Komplexität.



  • Warum stellst du deine Hausaufgaben nicht komplett am Stück ein? Dann können wir sie viel schneller für dich erledigen.



  • @Swordfish Danke dir !



  • @manni66 die Aufgaben sind Aufgaben von Altklausuren , sie haben keine Lösungen ,darum weiß ich nicht , welche Aufgaben , die ich einstellen muss.



  • Mach n zu einem Template Parameter, dann ist die Laufzeit konstant.



  • @TGGC ^^



  • @TGGC sagte in Frage nach Effizienz:

    Mach n zu einem Template Parameter, dann ist die Laufzeit konstant.

    Man kann auch argumentieren, dass die meisten praktischen Algorithmen nur Probleme lösen, bei denen n <= numeric_limits<size_t>::max() und somit so ziemlich alles was wir tagtäglich machen O(1) ist. Schliesslich fragen wir auch nicht bei einer simplen Integer-Addition nach der O(n)-Komplexität (n=Anzahl der Integer-Bits) dieser Operation. Alles eine Frage der Perspektive und welche Frage man mit Komplexitätsbetrachtungen beantworten will 😉



  • Nicht wirklich. Ein Algorithmus der auf etwas wie "lies n Speicherstellen" oder "schreibe n Speicherstellen" hinausläuft, ist auch bei vorher bekannten Werten für n immer linear. Und praktische Probleme sind meist dieser Art.



  • @TGGC sagte in Frage nach Effizienz:

    Nicht wirklich. Ein Algorithmus der auf etwas wie "lies n Speicherstellen" oder "schreibe n Speicherstellen" hinausläuft, ist auch bei vorher bekannten Werten für n immer linear. Und praktische Probleme sind meist dieser Art.

    Worauf ich hier (scherzhaft) hinaus will ist, dass man die praktischen Probleme so betrachten kann, dass n nie größer als eine Konstante ist.

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

    Die Idee mit dem size_t ist, das, was ich als "Problemgröße" betrachte umzudefinieren und alle (praktischen) Probleme mit einem solchen "äußeren O(1)-Algorithmus" zu erschlagen. Das macht natürlich keinen real laufenden Algorithmus wirklich schneller, aber das Ganze ist ja auch nicht wirklich ernst gemeint 😉


  • Mod

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



  • @SeppJ Hat meine Annahme oben denn gepasst?


  • Mod

    @Swordfish sagte in Frage nach Effizienz:

    @SeppJ Hat meine Annahme oben denn gepasst?

    Ja!



  • @SeppJ Thank You, Sir! High praise!

    ich bin einfach davon ausgegangen, daß der ganze quatsch in den loop-bodies auf handelsüblichen CPUs O(1) ist und somit zu ignorieren.


  • Mod

    @Swordfish sagte in Frage nach Effizienz:

    @SeppJ Thank You, Sir! High praise!

    ich bin einfach davon ausgegangen, daß der ganze quatsch in den loop-bodies auf handelsüblichen CPUs O(1) ist und somit zu ignorieren.

    Das ist sicher richtig, aber nicht im Sinne der Aufgabenstellung. Man will ja beurteilen, welche Effizienzklasse der Algorithmus bzw. dieses Schleifenmuster hat. Denk dir in jeder Schleife als Körper einen nicht-optimierbaren Funktionsaufruf von O(1). Wäre bloß noch unübersichtlicher für die Aufgabe, wenn man den stets hinschreiben würde, wo es hier doch um theoretische Informatik und nicht um Compileroptimierung geht.

    PS: Wobei das natürlich nicht die CPU optimiert, sondern der Optimizer, dem es egal sein sollte, was die Zielplattform wäre. Da nichts gemacht wird, würde ein moderner Optimizer auch für einen Uraltcomputer einfach einen leeren Body generieren. Da die Variablen int sind kann man nicht einmal mit Klugscheißereien bezüglich Überläufen kommen, da der Optimizer annehmen darf, dass die Schleife irgendwann abbricht.



  • @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.


Anmelden zum Antworten