Kleinste Zahl

garfield7554

Hallo

Kann mir jemand einen guten Algorithmus sagen wie ich am besten aus n Zahlen die kleinste herausfind ???

SirLant

garfield7554 schrieb:

Hallo

Kann mir jemand einen guten Algorithmus sagen wie ich am besten aus n Zahlen die kleinste herausfind ???

Wenn sortiert mit binärer suche, sonst musst du jedes Element durchgehen.

otze

ich geh einfach mal davon aus, dass du ein array benutzt.

int n[100];
//hier array füllen
int zahl=n[0];
for(int i=1;i<100;++i){
    if(zahl>n[i]){zahl=n[i];
}

CarstenJ

Hallo,

Wenn sortiert mit binärer suche, sonst musst du jedes Element durchgehen.

wenn es sortiert ist, dann brauch ich doch nur die erste Zahl nehmen (bzw. die letzte)......

keine ahnung, on dir dieser algo gefallen wird, aber er funktioniert ...

int min ( int* array, const std::size_t size )  {
  for ( int i = 1; i < size; ++i )
    array [ i ] = array [ i ] < array [ i - 1 ] ? array [ i ] : array [ i - 1 ];
  return array [ size - 1 ];
};

was auch immer

SirLant

CarstenJ schrieb:

Hallo,

Wenn sortiert mit binärer suche, sonst musst du jedes Element durchgehen.

wenn es sortiert ist, dann brauch ich doch nur die erste Zahl nehmen (bzw. die letzte)......

Stimmt, hatte irgendwie ans finden allgemein gedacht

Ne dann bleibt nur zu suchen, weil bei nem unsortierten hast du keinerlei
Anhaltspunkte. Du könntest höchstens Stichprobenartig suchen, erst jedes
5.Element, dann jedes 3, jedes 2. am schluss jedes Einzelne, könnte die
Dauer verkürzen, aber im ungünstigen Fall unnötig verlängern, außer du
Suchst rein zufällig und speicherst welche Elemente du bereits durchsucht hast.
So könntest du es finden und wäre im schlimmsten Falle nur wegen dem Speicheroverhead
und dem zufälligen durchsuchen etwas langsamer.

Jester

Das ist doch völliger Quatsch.

Wenn die Zahlen gleichmäßig verteilt sind, dann wirst Du im Mittel n/2 Zahlen anschauen müssen. Egal in welcher Reihenfolge Du das tust. Also brav von Anfang bis Ende durchlaufen, dann bist Du von der Komplexität her optimal, der average-case stimmt auch und die Implementierung ist super einfach. Was will man mehr?

Bashar

SirLant schrieb:

Du könntest höchstens Stichprobenartig suchen, erst jedes
5.Element, dann jedes 3, jedes 2. am schluss jedes Einzelne, könnte die
Dauer verkürzen, aber im ungünstigen Fall unnötig verlängern, außer du
Suchst rein zufällig und speicherst welche Elemente du bereits durchsucht hast.

Wie soll das funktionieren? Solange es auch nur ein Restelement gibt, was du nicht untersucht hast, weißt du nicht, ob du das kleinste Element schon gefunden hast oder ob vielleicht gerade dieses eine Restelement das kleinste ist. Daraus folgt, dass du grundsätzlich alle Elemente untersuchen musst. In welcher Reihenfolge du vorgehst, ist eigentlich völlig egal, aber in "ausgeklügelten" Mustern darüberzulaufen ist reiner Voodoo.

Shade Of Mine

std::min_element()?

SirLant

Bashar schrieb:

SirLant schrieb:

Du könntest höchstens Stichprobenartig suchen, erst jedes
5.Element, dann jedes 3, jedes 2. am schluss jedes Einzelne, könnte die
Dauer verkürzen, aber im ungünstigen Fall unnötig verlängern, außer du
Suchst rein zufällig und speicherst welche Elemente du bereits durchsucht hast.

Wie soll das funktionieren? Solange es auch nur ein Restelement gibt, was du nicht untersucht hast, weißt du nicht, ob du das kleinste Element schon gefunden hast oder ob vielleicht gerade dieses eine Restelement das kleinste ist. Daraus folgt, dass du grundsätzlich alle Elemente untersuchen musst. In welcher Reihenfolge du vorgehst, ist eigentlich völlig egal, aber in "ausgeklügelten" Mustern darüberzulaufen ist reiner Voodoo.

Stimmt ja, schon wieder irgendwie falsch gedacht, man hat das zu vergleichende
Element ja gar nicht.
Heut ist echt nicht mein Tag, werd ab jetzt still sein