Suchen in mengen

[DaKa]

Hallo,

muss bis nächsten Montag folgende Aufgabe lösen:

*******************************************

AUFGABENSTELLUNG:

gegeben sei ein Feld der Länge n. Ab wie vielen Suchanfragen lohnt sich eine binäre Suche im Vergleich zu einer sequentiellen Suche? (wir gehen vom worst-case aus)

Es gilt zu beachten, dass die binäre Suche eine Vorsortierung der Daten voraussetzt. Dies ist durch einen Zeitaufwand von O(n log n) möglich.

*******************************************

ÜBERLEGUNGEN:

• worst-case sequentielle Suche: O(n) = Suchaufwand
  
• worst-case binäre Suche: log2(n) = Suchaufwand (= obere Schranke des Logarithmus von n zur Basis 2)
  
• binäre Suche: n*log(n) Sortieraufwand
  

der Sortieraufwand lohnt sich also wenn n>log2(n)+n*log(n)

Stimmt das? Wenn ja zu welcher zu welcher Basis gehört n*log(n) und wie bekomme ich heraus ab wie vielen Suchanfragen sich das lohnt.

Danke im voraus,

Viele Grüße

Dan

[lupo49]

(Beim Aufwand für das Vorsortieren meinst du O(n * log2(n)) und nicht den 10er-Logarithmus? Das wäre nämlich dann der minimale Aufwand, den ein Sortieralgorithmus realisieren kann.)

Den Ansatz würde ich auch nehmen. Wenn du die beiden Funktionen einmal Plotten lässt, dann siehst du, dass der Aufwand für die sequentielle Suche durch das Vorsortieren des Feldes sehr stark ansteigt. Ab n = 2,83... ( n = n * lb(n) + lb(n); Auflösen nach n = 2,83) ist die sequentielle Suche schneller als die Binäre Suche.

Was meinst du mit Basis?

[Klotzkopp]

der Sortieraufwand lohnt sich also wenn n>log2(n)+n*log(n)

Das ist eine Überlegung für eine einzige Suchanfrage. Die Frage ist, wie sich das entwickelt, wenn du mehrere Anfragen machst.

Wenn ja zu welcher zu welcher Basis gehört n*log(n)

Die Basis ist für solche Abschätzungen irrelevant. Sie wirkt sich nur in Form eines konstanten Faktors aus.

Du wirst hier auch keinen konkreten Wert ausrechnen können. Es wird darum gehen, in welcher Größenordnung im Vergleich zu n die Anzahl der Suchanfragen steht. Bei einer einzigen Suchanfrage ist die lineare Suche sicher schneller.

[flashpixx]

@Klotzkopp: Full Ack'

Ich verlinke einmal Landau-Symbole ? Wikipedia

Du wirst feststellen, wenn Du einmal die sequentielle Suche betrachtest und dagegen die binäre Suche, dass sich beide Aufwandskurven bei einem n scheiden und genau dieser Punkt wird gesucht, d.h. Gleichungen aufstellen und nach n auflösen.

Letztendlich hat das Lupo gemacht, wobei ich hier etwas korrigiere, dass n eine Zahl aus N ist, somit kann n nicht 2,... sein, sondern muss entsprechend mit dem Ceil-Operator auf die nächst größere natürliche Zahl abgebildet werden.

Zu Klotzkopps Ansatz: Da die Landau Symbole immer einen konstanten Faktor c beinhalten, kann man in der Praxis dieses auch optimieren, d.h. im Fall einer lineare Suche würde das bedeuten, dass man die Elemente, die häufiger gesucht werden, an den Anfang des Arrays gestellt werden. D.h. ein Element das häufiger gesucht wird wird somit eben schneller gefunden. Die Suche ist zwar immer noch linear, aber eben hat für "häufige" Elemente ein kleineres c, so dass eben der Aufwand in der Praxis kleiner wird. Schwierig wird es nur eine solche Optimierung zu finden, denn die zentralen Fragen sind, wie ermittelt man die "häufigsten" Elemente und was passiert, wenn nun die "schlechten" Elemente häufiger gesucht werden, das umsortieren des Arrays muss man formal auch mit in den Aufwand einrechnen

[DaKa]

Hallo,

vielen Dank für Eure ausfürhlichen Antworten!

habe jetzt folgendes vorgehen gewählt:

- die Funktionen

f(x)=n [max. Aufwand (sequentielle Suche)]

und

g(x)=log(n)+n*log(n) [max. Suchaufwand + Sortieraufwand (binäre Suche)]

plotten lassen.

Den Schnittpunkt bestimmt (liegt bei ca. S(1,5|1,5)). Allerdings steigt die Funktion n*log(n)+log(n) viel schneller an, als n und daher ist das mit der Behauptung binäre Suche sei schneller nicht schlüssig.

Danke,

Viele Grüße

Dan

[Klotzkopp]

habe jetzt folgendes vorgehen gewählt:

Da ist immer noch nichts von der Anzahl der Suchvorgänge zu sehen. n ist nicht die Anzahl der Suchvorgänge, sondern die Anzahl der Elemente in der Menge. Was du gezeigt hast, ist die Situation für eine Suchanfrage. Da ist es klar, dass die sequentielle Suche schneller ist.

Du sollst untersuchen, wie sich das bei mehreren Suchanfragen entwickelt.

[DaKa]

mhhh OK, das stimmt... also müsste es heißen

g(x)=x*n [seq. Suche]

f(x)= x*(n*log(n)+log(n)) [binäre Suche]

wobei x die Anzahl der Suchanfragen und n die Größe des Arrays ist?

Dann komme ich aber immer noch nicht weiter. Sorry habe gerade glaube ich ein Brett vor dem Kopf bei der Aufgabe..

Wohin muss ich das auflösen bzw. wie in Verbindung setzen, um allgemein die Anzahl der Suchanfragen zu erhalten, ab der sich die binäre Suche lohnt?

[lupo49]

g(x)=x*n [seq. Suche]

f(x)= x*(n*log(n)+log(n)) [binäre Suche]

Das Sortieren des Feldes passiert nur einmalig imho. Also müsste es lauten n*log(n) + x*log(n).

Meine Ansatz:

Die sequentielle Suche ist generell langsamer als die binäre Suche (vorausgesetzt das Feld ist vorsortiert). Aber in diesem Fall ist das Feld nicht sortiert. D.h. das Feld muss zu Beginn einmalig sortiert werden, um den schnelle binären Algorithmus anwenden zu können.

Beim ersten Aufruf beider Suchalgorithmen ist die binäre Suche so langsam, weil das Feld nicht sortiert ist. Also wird erst das Feld sortiert und dann gesucht. Wenn die Suche erneut gestartet wird, ist das Feld bereits sortiert und der Aufwand fürs Sortieren fällt weg (n*log(n)). Somit müsste doch dann ab der zweiten Suche die binäre Suche immer schneller sein?

[flashpixx]

Somit müsste doch dann ab der zweiten Suche die binäre Suche immer schneller sein?

Im Normalfall geht man ja nicht von einem statischen n aus. Nimm' z.B. einmal die Primärschlüssel einer Datenbank und den darauf angewendeten select. D.h. Du musst "ständig" neu sortieren, da sich das Datenfeld ändert. Hierzu verwendet man dann entsprechende mittlere, untere und obere Abschätzungen

[lupo49]

Wenn das Feld bzw. die Datenquelle vor jedem Suchlauf neu sortiert werden muss, dann wird die binäre Suche doch nie schneller sein?

Oder läuft es so ab, dass man einmalig sortiert und dann beim Hinzufügen von neuen Elemente, die Elemente direkt an der korrekten Stelle einpflegt?

[flashpixx]

Oder läuft es so ab, dass man einmalig sortiert und dann beim Hinzufügen von neuen Elemente, die Elemente direkt an der korrekten Stelle einpflegt?

Naja so einfach ist das ganze nicht. Man kann bei jedem Einfüge / Löschen / Ändern neu sortieren oder man sortiert eben in gewissen Zeitabständen oder man sortiert, wenn die Daten einen gewissen "Unordnungsgrad" erreicht haben. Bei Datenbanken führt das DBMS eben "Buch" darüber wie effizient aktuelle Suchanfragen sind und optimiert dann in gewissen zeitlichen Abständen die Daten. Das ganze wird aber nicht mehr analytisch berechnet sondern man macht das ganze mit entsprechenden Abschätzungen der Verteilung der Laufzeiten der Anfragen. Man versucht halt damit die Mittel notwendige Zeit zu einer Suchanfrage optimal (minimal) zu bekommen

Bearbeitet 13. Juni 2010 von flashpixx

[Klotzkopp]

Da in der Aufgabenstellung steht

gegeben sei ein Feld der Länge n.

gehe ich davon aus, dass zwischen den Suchvorgängen keine Daten hinzukommen. Es reicht also, einmal am Anfang zu sortieren.

[Mcolli]

Hallo:

ich habe mal die Lösung ausgerechnet für dich

im folgenden gilt das "log2(n)" (<-zur Basis) zwei als "ld(n)" geschrieben wird und mit "log(n)" ist der Logarithmus zur Basis 10 gemeint!!!

"a" steht für die Anzahl der Suchanfragen die bei der binären Suche keine Neusortierungen nach einmaliger Sortierung vorraussetzt.

"n" steht für die Anzahl an Elementen in der zu durchsunden Menge.

a,n sind Element der Natürlichen Zahlen und ungleich 0.

Du hast für die Berechnung des Binären - Suchaufwandes ld(n) angegeben und für die Berechnung des Sortieraufwandes n*log(n).

Damit hat mein 2 verschiede Logarithmenbases in der Gleichung und man muss transformieren, was die Lösung der gleichung meiner Meinung nich Hausaufgaben gerecht macht.

Ich denke daher dass die Berechnung des Sortieraufwandes n*ld(n)

Ich habe beides durchgerechnet:

1. Sortieraufwand n*ld(n)

a * n < a * ld(n) + n * ld(n) = ld(n) * (a + n)

<-> es gilt a + n > 0

(a * n) / (a + n) < ld(n)

<-> Umkehren

(a + n) / (a * n) > 1 / ld(n)

<-> linke Seite in 2 Brüche teilen

(a / a * n) + (n / a * n) > 1 / ld(n)

<-> Kürzen

(1 / n) + (1 / a) > 1 / ld(n)

<-> 1 /n abzeiehn

1 / a > 1 / ld(n) - 1 /n

<-> Rechte Seite Normieren

1 / a > (n - ld(n)) / ld(n) * n

<-> Umkehren

a < ld(n) * n / (n - ld(n))

Kosmetische Eingreife auf der rechten Seite evtl noch möglich

2. Sortieraufwand n*log(n)

Ich hab eine Office Datei Angehängt in der das mit besserer formatierung gerechnet wird .... ist ein wenig komplexer und ein paar mehr Kniffe und Gefühl ist erforderlich.

soviel sei aber gesagt je größer n wird desto besser trifft diese vereinfachung zu:

Für

a < log(n)

ist approximal eine Lineare Suche im Worstcase effektiver.

Zu der Frage wir das Nie schneller wenn immer Sortiert wird:

a * n < a * (log(n) + n * log(n))

<-> es gilt a != 0

n < log(n) + log(n) * n

da 1 <= log(n) für alle n Element N

n < 1 + 1 * n < = log(n) + log(n) * n

<->

n < n + 1 <= log(n) + log(n) * n

also ist die Binäre Suche in dem Fall immer größer als n + 1

=> immer einmal Langsamer

Man kann a möglichst Großhalten und Gewehrleisten dass immer Sortiert ist wenn man

sich merkt "ist n größer geworden" wenn ja vor der nächsten Suchanfrage einmal sortieren.

Lösung.doc

Lösung.odt

Bearbeitet 20. Juni 2010 von Mcolli

[flashpixx]

a * n < a * ld(n) + n * ld(n) = ld(n) * (a + n)

[..]

soviel sei aber gesagt je größer n wird desto besser trifft diese vereinfachung zu:

Für

a < log(n)

ist approximal eine Lineare Suche im Worstcase effektiver.

Woher nimmst Du die Voraussetzung, dass a*n < ld(n) * (a+n) ist? Du steckst im Grunde in Deine Voraussetzung schon hinein, dass die lineare Suche kleiner ist, als die binäre. Damit hast Du aber keinen formalen Schluss, denn Du zeigst nur durch die Umformung, dass Deine Behauptung stimmt, d.h. ich kann genauso zeigen, dass 2 < 3 ist, denn 2-3 < 0 ist immer erfüllt. Ich denke der Ansatz ist schon okay, nur würde ich das ganze über einen Induktion beweisen, denn wenn dann entsprechend die (strengen) Monotonieeigenschaften vorliegen bzw. der Quotient aus linearer zu binärer Suche ebenfalls im Limes monoton fallend / wachsend ist, hast Du den passenden Schluss

[Mcolli]

Woher nimmst Du die Voraussetzung, dass a*n < ld(n) * (a+n) ist? ...

Tue ich nicht. Ich weiss aus der Aufgabenstellung, dass der Gesammtaufwand für EINE EINZIGE Lineare Suche "n" ist. Desweiteren weiss ich, dass der Gesammtaufwand für EINE EINZIGE binären Suche "Suchaufwand + Sortieraufwand" ist.

In der Aufgabenstellung steht für die binäre Suche

Suchaufwand = ld(n)

Sortieraufwand = n * ld(n)

-> "Suchaufwand + Sortieraufwand" = ld(n) + n * ld(n)

Wenn man mehr als einmal sucht gilt "Mehrfache Suche = Suchanzahl * Gesammtaufwand".

also:

lineare "Mehrfache Suche" = a * n

Für die binäre gehe ich bei 1. davon aus, dass NICHT neusortieren werden muss für jede Sucheanfrage aus a ... Warum ich das mache steht ganz unten: "Die Aufgabe wäre sonst schwachsinnig"

-->

binäre "Mehrfache Suche" = a * Suchaufwand + Sortieraufwand = a * ld(n) + n * ld(n)

Die Frage lautet jetzt wann ist die lineare Mehrfachsuche der binären Mehrfachsuche überlgen. Also mathematisch Ausgedrückt

Für welche a element {N}gilt

a * n < a * ld(n) + n * ld(n)

alles was ich danach mache nennt sich Mathematik.... zugegeben ich bin ein wenig eingerostet was das angeht aber ich habe nach den Regeln der Mathematik umgeformt. Bei deiner Zeile z.B. habe ich "ld(n)" ausgeklammert

-> a * ld(n) + n * ld(n) = ld(n) * (a + n)

dann immer weiter Umformen bis irgendwann etwas da steht wie

a < f(n)

mit f(n): {N} -> {R}

Wenn man ein n hat kann man den Funktionswert bilden. WEnn die Anzahl der Suchanfragen kleiner ist als der Funktionswert ist die lineare Suche besser.

Bearbeitet 20. Juni 2010 von Mcolli

[flashpixx]

a * n < a * ld(n) + n * ld(n) = ld(n) * (a+n)

Diese Voraussetzung ist immer für ein n und a > 0 erfüllt, denn ln / log / ld sind streng monoton wachsende Funktionen. (a+n) ist immer <= a*n (da a und n aus N sind und man hier über die Monotonie zeigen, dass a*n stärker wächst als a+n).

Wenn ich nun noch mit einer streng monoton wachsende Funktion multipliziere, ändert das nichts an der Ungleichung, somit folgt eben nur, dass Deine Voraussetzung erfüllt ist

[Mcolli]

Diese Voraussetzung ist immer für ein n und a > 0 erfüllt, denn ln / log / ld sind streng monoton wachsende Funktionen. (a+n) ist immer <= a*n (da a und n aus N sind und man hier über die Monotonie zeigen, dass a*n stärker wächst als a+n).

Wenn ich nun noch mit einer streng monoton wachsende Funktion multipliziere, ändert das nichts an der Ungleichung, somit folgt eben nur, dass Deine Voraussetzung erfüllt ist

Beispiel:

Es gibt 10000 Suchanfragen auf eine Menge mit 5 Elementen

Also a = 10000 und n = 5. Somma jetzt binär oder linear Suchen.

Wir nehmen meine Ungleichung

a * n < ld(n) * (a+n)

links:

10000 * 5 = 50000

rechts:

ld(5) * 10005 = 23239,89....

--> linkeSeite > rechte Seite --> ungleichung nicht immer erfüllt.

Wir sehen die Ungleichung ist NICHT immer erfüllt

Du hast zwarch recht das beide Funktionen (sogar Streng) Monoton steigen aber d.h. NICHT, dass die Steigung wie bei der geraden "a * n" auch imemr Konstant ist. Du gehst schon gut mit dem "ersetzen" bei Ungleichung um.

Ich schreib nachher noch mal mehr ich muss jetzt schnell weg.

Nur soviel die rechte Seite ist im Kern eine logaritmische Funktion und diese Art von Funktionen steigen immer weniger irgendwann ist die steigung < a und dann wird der 2. Term (a+n) immer kleiner ....

rechte Seite ableiten gucken ob streng monoton fallend.... Grenzwert gibts da auch für n -> unendlich

[flashpixx]

Beispiel:

Wir sehen die Ungleichung ist NICHT immer erfüllt

Du hast zwarch recht das beide Funktionen (sogar Streng) Monoton steigen aber d.h. NICHT, dass die Steigung wie bei der geraden "a * n" auch imemr Konstant ist. Du gehst schon gut mit dem "ersetzen" bei Ungleichung um.

Sämtliche Abschätzungen werden im Limes betrachtet, d.h. a und n müssen gegen unendlich laufen.

Siehe dazu den Landau Wikipedia Artikel:

Landau-Symbole werden in der Mathematik und in der Informatik verwendet, um das asymptotische Verhalten von Funktionen und Folgen zu beschreiben.

Du betrachtest bei Deine Umformung keine Folge oder Funktion, sondern formst nur einfach eine Ungleichung um. Bei der Abschätzung spielt es keine Rolle, ob sich nun endlich viele Beispiele finden lassen, wo es nicht zutrifft, sondern wie das Verhalten im Unendlichen aussieht (ich reduziere es einmal auf die Definition des Grenzwertes, dass es endliche viele Elemente in der Folge gibt die eben über einer Schranke und unendliche viele unterhalb einer Schranke liegen).

Außerdem steht jetzt Deine Aussage, das die Ungleichung eben nicht immer erfüllt ist zu Deiner ersten Aussage

[...]ist approximal eine Lineare Suche im Worstcase effektiver.

im Widerspruch, denn in Deiner Umformung hast Du den Grenzprozess nicht durchgeführt. Du führst hier lediglich den Schluss an, dass für limes a -> inf: a < limes n -> inf: ln(n) gilt, denn das würde dem "worst-case" entsprechen. Damit würdest Du sagen, dass der Aufwand für eine Suche nicht von der Anzahl der der Suchanfragen bzw zu der Anzahl der zu durchsuchenden Elemente wäre. D.h. Anzahl Suchanfangen und Elementanzahl wären unkorreliert.

Eine rein analytische Umformulierung der Gleichung wird hier nicht ausreichend, sondern man muss eben eine allgemeingültige Abschätzung für den Limes oder eine Induktion über n und a durchführen.

Bearbeitet 20. Juni 2010 von flashpixx

[DaKa]

Hallo,

vielen lieben Dank für die ganzen ausführlichen Antworten.

Habt mir sehr weitergeholfen und denke es jetzt verstanden zu haben :-)

Viele Grüße

[Mcolli]

Wenn man zwei funktionen in ein Koordinaten System eintragen will und beide Funktionen von einer Variablen abhängig sind ist das eh wurst. Deshalb habe ich ja auch versucht a und n in der Ungleichung zu trennen.

Mal zurück zum Kern:

1. Dem Ersteller des Threads wurde von wem auch immer wie auch immer geholfen.

2.

Dein Problem jetzt mit meiner Lösung zur Aufgabe (1.Post) habe ich nicht verstanden.

(Statt f(a,n) und g(a,n) sollte man besser fn(a) und gn(a) schreiben da das mathematisch der Darstellung eine Funktionsschar gleicht aber das dauert ewig zu formatieren hier)

Meine Idee: den Aufwand von linear mit binär Vergleichen

Mein Vogehen:

• zwei Formeln aufstellen: f(a,n) und g(a,n). f(a,n) beschreibt den linearen Suchaufwand und g(a,n) beschreibt den binären Suchaufwand.
  
• Diese Formeln in eine Relationsätzen die zu der Frage passt "Ab welchem a und bei einem Konstanten n ist die binäre Suche besser". f(a,n) < g(a,n)
  
• Die daraus Resultierende Ungleichung nach a "umstellen" also
  a < g '(n).
  
• Die Formel kann die Frage aus der Aufgabenstellung für jedes n beantworten:
  Es dürfen maximal g '(n) Suchanfrage auf eine Menge mit n Elementen gestellt werden damit die lineare Suche effizienter ist.
  

Was meinst Du ist Falsch?

1. Die Formeln zur Auwandsberechnung

2. Das Setzen der Realtion

3. Die Schlussfolgerung

Zum Grenzwert:

Es wäre sicher auch interessant aus mathematischer Sicht die Funtkionsscharen

f(a,n) = a * n und g(a,n) = a * ld(n) + n * ld(n)

zu untersuchen. Dies ist für die Aufgabe aber TOTAL irrelevant da sich die Frage der Aufgabenstellung darauf bezieht zwei einzelene Funktionen aus den Funtionsscharen zu vergleichen: In dem Moment in dem man sich die Frage stellt "soll ich so oder so suchen in der Menge M" suchen ist n bekannt und keine Variable mehr.

Die Frage ist nicht "Um wieviele Elemente hätte meine Menge M größer sein müssen". Es werden aus beiden Scharen die n-ten Funktionen verglichen und nur a ist Variable.

Die Mathematische Untersuchung anders wäre dann:

existiert kein a für das gilt:

für alle i element {N} gilt:

fn(a + i) < gn(a + i)

aber damit kannst Du nur sagen "ja/nein, so ein a gibt es (nicht) für dieses n"

Meine Lösung gibt auch an wie groß dieses a sein muss. Das ist auch das was gefragt ist. Wenn der rechte Teil meiner umgeformenten Funktionsgleichung für alle n einen Funktionswert hat kann man sogar sagen, dass alle Mengen mit endlich vielen Elementen ab einem a besser binär Durchsucht werden.

Besser kann ich das was ich meine jetzt echt nicht mehr erklären.

Bearbeitet 20. Juni 2010 von Mcolli

[flashpixx]

(Statt f(a,n) und g(a,n) sollte man besser fn(a) und gn(a) schreiben da das mathematisch der Darstellung eine Funktionsschar gleicht aber das dauert ewig zu formatieren hier)

Ist zwar nur Notation, aber da gebe ich Dir recht

Meine Idee: den Aufwand von linear mit binär Vergleichen

Ist auch klar, ist auch soweit in meinem Sinn.

Es dürfen maximal g '(n) Suchanfrage auf eine Menge mit n Elementen gestellt werden damit die lineare Suche effizienter ist.

Ich denke, dass er Schluss, den Du ziehst, nicht okay ist.

Es wäre sicher auch interessant aus mathematischer Sicht die Funtkionsscharen

f(a,n) = a * n und g(a,n) = a * ld(n) + n * ld(n)

zu untersuchen.

Ich denke, dass hier wäre das richtige, denn Deine Ungleichung liefert ja, dass a und n unkorreliert sind. Du formst ja soweit um, dass Du irgendwann sagst, so lange a kleiner als ld(n) ist, lohnt sich eine binäre Suche nicht. Da wir ja eine Funktionsschar haben, müssten wir ja eigentlich ein a oder n fest wählen und uns dann für das andere das Optimum suchen. Im gleichen Zug müssten wir das dann wieder umgekehrt machen, d.h. wir betrachten die Asympotik einmal für fest n und einmal für festes a

Letztendlich würde das eben darauf hinauslaufen, dass wir uns anschauen, wie sich die Funktionsscharen für binäre und lineare Suche im Limes verhalten und wir dann das einen Schnittpunkt bzw mehrere Schnittpunkte finden.

[Mcolli]

Ich denke, dass hier wäre das richtige, denn Deine Ungleichung liefert ja, dass a und n unkorreliert sind. Du formst ja soweit um, dass Du irgendwann sagst, so lange a kleiner als ld(n) ist, lohnt sich eine binäre Suche nicht. Da wir ja eine Funktionsschar haben, müssten wir ja eigentlich ein a oder n fest wählen ....

Meiner Meinung nach, wie schon oben gesagt, geht die Aufgabenstellung aber eindeutig davon aus, dass man für ein konkretes n wissen will, wie viele Suchanfragen nötig sind damit die binäre Suche effizienter wird, trotz einmaligen Sortieren.

Das hätte nämlich auch einen konkreten praktischen Nutzen beim Programmieren.

Wenn man statt die Funktionsscharen mit n zu parametrisieren mit a parametrisiert, also das Problem von der andern Seite betrachtet, kann man Aussagen ala "Ab wievielen Mengenelementen lohnt sich für 10 Suchanfragen die binäre/lineare Suche" beantworten.

Ich hab keine Ahnung welche Aussage man treffen möchte wenn man a und n als Variable betrachtet.

Naja evtl meldet sich der Thredersteller ja noch mal.

Zu min. ist es mal schön über Mathe auf vernünftigen Niveau zu diskutieren ohne dass jemand aus Desintresse auf Durchzug schaltet.

[Mcolli]

//edit noch was eingefallen

Letztendlich würde das eben darauf hinauslaufen, dass wir uns anschauen, wie sich die Funktionsscharen für binäre und lineare Suche im Limes verhalten und wir dann das einen Schnittpunkt bzw mehrere Schnittpunkte finden.

Für den lienaren Aufwand gilt ja

a * n

Wenn man jetzt z.B. "n" parametrieserit wird ja "a" auf der Abszisse abgetreagen. Somit ist n die Steigung. Wenn man das nicht konkretisiert sonder auch im Limes betrachtet ist die Steigung im Grenzwert unendlich .... also platt gesagt eine Relation.

Wenn ich mal den binären Aufwand

a * ld(n) + n * ld(n)

vereinfache enthält man ja

ld(n^a * n²) = ld (n^(a+1))

also eine Logarithmische Funktion, die immer steiler wird. Also wird der "geradenähnliche Teil" vor dem "Knick" ja immer länger und steiler und der Knick imemr "spitzer" (kenn das von FET-Kenlinienfeld). Somit müssten ja beide Scharen im limes n und a -> unendlich ewiglang an der Ordinate "kleben". Zugegeben ist sehr bildlich gesprochen aber ist ja auch nur ne theorie wo ich genau jetzt --- nein JETZT keine Zeit mehr hab bis später.

[flashpixx]

Zu min. ist es mal schön über Mathe auf vernünftigen Niveau zu diskutieren ohne dass jemand aus Desintresse auf Durchzug schaltet.

Da kann ich nur full Ack' zu sagen. Danke für die Diskussion