SELECT Feld vergleichen

[PalimPalim123]

Hey,

ich hab folgende Aufgabe im Studium und weiß nichts recht damit anzufangen:

An element of an array A is a winner if it is stored in A more than length(A)/2 times. Clearly, an array does not necessarily have a winner.

Suppose you can perform comparisons on the elements of the array. The comparison test can give 3 possible outcomes: <, >, = .

Using SELECT find a Winner in O(n) comparisons. Make sure your algorithm correctly determines whether a winner exists.

Ich steh da ziemlich auf dem schlauch. Kann mir vielleicht jemand weiterhelfen? Danke im Voraus.

lg

[smash]

Was hast du dir denn bisher überlegt?

Also gehen wir doch mal ein paar einfache Situationen durch:

A.length() = 0;

Array leer. Es gibt nicht mal einen potentiellen Gewinner.

A.length() = 1;

1/2 = 0.5

Also wenn es ein Element in A gäbe, dass mehr als 0.5 mal in A gespeichert wäre, wäre es ein Gewinner. Da ja ein Element 1 mal in ja ist und 0.5 < 1 wäre das Element immer ein Gewinner.

A.length() = 2;

2/2 = 1

Es müssten schon beide Elemente gleich sein. Dann wäre das Element also 2 mal in A und 1 < 2. Es wäre ein Gewinner.

A.length() = 3;

3/2 = 1.5;

Ein Element muss mindestens 2 mal in A sein, dann ist das Element ein Gewinner. Das dritte Element ist entweder auch dasselbe oder kein Gewinner.

Was hat das denn mit dem SELECT auf sich? Bezieht sich die Aufgabe auf eine konkrete Sprache? Es hörst sich nach SQL an, aber da gibt es doch keine Arrays oder? Vielleicht in Stored Procedures. ODer steht das SELECT nur für eine Fallunterscheidung wie "if"?

Das mit O(n) ist die Laufzeit-Komplexität. Da bin ich jetzt leider auch nicht sattelfest. Es darum, wie viele Rechenschritte dein Algorithmus benötigt um Gewinner zu ermitteln in Abhängigkeit der Anzahl der Elemente.

Zeitkomplexität ? Wikipedia

Landau-Symbole ? Wikipedia

Ich glaube, wenn man das (oder den?) Array durchlaufen würde und die Häufigkeit der Elemente zählt, kommt man höchstens auf O(n) oder bleibt darunter. Ohne Gewähr.

Bearbeitet 16. September 2010 von smash

[flashpixx]

Ich glaube, wenn man das (oder den?) Array durchlaufen würde und die Häufigkeit der Elemente zählt, kommt man höchstens auf O(n) oder bleibt darunter. Ohne Gewähr.

Das ist so nicht ganz korrekt, wenn Du Häufigkeit der Elemente ermitteln willst, wäre ein naiver Ansatz das Array einmal zu durchlaufen, um festzustellen, welche Daten enthalten sind (nennt sich Buckets). Nach dem Lauf weiß man, welche unterschiedlichen Buckets vorhanden sind. Nun muss ich für jeden Bucket die Häufigkeit ermitteln, d.h. das Array für jedes Bucket durchlaufen. Das macht im wort-case ein O(n^2), denn wenn jedes Array-Element verschieden von den anderen ist und das Array selbst n Elemente enthält, dann erhalte ich n Buckets. In jedem Bucket steht dann logischerweise eine 1 drin, da jedes Element einmal vorkommt.

Es gibt natürlich effizientere Verfahren Häufigkeiten zu ermitteln.

Der Beweis lässt sich durch vollständige Induktion zeigen