Suche nach Minimalwert -> WIE?



  • Hallo!
    Ich habe ein Problem, bei dem ich nicht weiss wie es elegant zu lösen geht:
    Da hab ich mehrere Werte (jeder davon hat einen bestimmten Ursprung) und möchte nun von all diesen Werten den kleinsten heraussuchen (der Ursprung sollte danach noch immer ersichtlich sein).
    Es wäre möglich die Werte jeweils in eine eigene Int-Variable zu schreiben, oder auch die Werte in ein Array[] zu schreiben und danach irgendwie die Auswertung zu beginnen. Und das ist nun meine Frage, wie kann ich den Minimalwert herausfinden. Ich könnte es mit einer Wurst an if()-Abfragen machen, aber diese Methode wäre doch nicht elegant....

    Danke für eure Hilfe!
    Mario



  • na wenn du alle möglichen kandidaten in einem array hast, dann kannst du das einfach einmal durchlaufen und hast dein minimum. das geht in konstanter zeit und ist rasend schnell

    min = array[0];
    for(int i = 1; i < array_size; ++i)
     if(array[i] < min) min = array[i];
    

    alternativ nur den index speichern



  • thordk schrieb:

    .....dann kannst du das einfach einmal durchlaufen...... das geht in konstanter zeit ...

    Hmmh,das muss ja nen geiler Algorithmus sein der n-Iterationen macht und trotzdem ne Laufzeit von O(1) hat.Das grenzt sozusagen an ein Wunder 😉

    MfG Spacelord



  • bleh, der zugriff is konstant. jedes objekt einmal anfassen musst bei nicht vorsortierten daten eh.



  • Hallo Mario,

    wenn's elegant sein soll und der Ursprung der Variable nicht verloren gehen soll, so nutze std::min_element.

    int array[] = { 3, -2, 9, 7 };
        const int array_size = sizeof( array )/sizeof( *array ); 
        int* pMin = std::min_element( array, array + array_size );
    

    liefert Dir den Iterator (bei Arrays den Pointer) auf das kleinste Element.
    Erfordert #include <algorithm>

    Gruß
    Werner



  • @thordk: Wie Spacelord schon angedeutet hat, ist die Zeitkomplexität beim Suchen des Minimalwerts in einem unsortierten Container nicht konstant, sondern linear. In O Notation lautet die Schrankenfunktion O(n). Jedes Objekt konstant-oft anzufassen, bedeutet, dass die Häufigkeit des Anfassens im Bezug auf die Anzahl der Objekte linear ist. Konstante Komplexität wäre gegeben, wenn die Häufigkeit des Anfassens bei Veränderung der Objektanzahl konstant bleiben würde. Wenn der Container also sortiert wäre, hätte man es mit konstanter Komplexität zu tun; man müsste dann nämlich bei jeder Objektanzahl immer nur vorne und/oder hinten anfassen.


Log in to reply