Algorithmus anzahl(a,b) für Counting-Sort?

Question

Aufgabe:

Geben Sie Pseudocode an, der es ermöglicht, für n ganze Zahlen aus [0,...,k] nach einem Vorverarbeitungsschritt Anfragen der Form anzahl(a, b) in konstanter Zeit zu beantworten. anzahl(a, b) soll ausgeben, wieviele der Eingabezahlen im Bereich [a,b] liegen. Der Vorverarbeitungsschritt sollte Zeit Θ(n + k) benötigen.

Ansatz/Problem:

Meine Idee war einfach, das Count Array zu nehmen, es dann von C[a] bis C[b] durchzugehen und zu checken ob eine 1 drin vorkommt oder nicht, wenn ja den Zähler erhöhen, sodass ich bei der Methode anzahl(a, b) auf diesen Zähler zurückgreifen kann. Macht das Sinn?

Answer 1

Antwort mit KI erzeugt

Lösungsidee & Pseudocode

Deine Idee, Counting Sort als Basis zu verwenden, ist ein guter Ansatz. Jedoch beinhaltet die direkte Iteration von \(C[a]\) bis \(C[b]\) im anzahl(a, b) Aufruf nicht das Erreichen der Anforderung, Anfragen in konstanter Zeit (\(O(1)\)) zu beantworten. Stattdessen solltest du die Präfixsummen innerhalb des Count-Arrays nutzen.

Vorverarbeitungsschritt:

1. Erstelle ein Count-Array \(C\) der Länge \(k+1\), initialisiert mit 0, wobei \(k\) das Maximum der Eingabezahlen ist.
2. Für jede Zahl \(x\) aus den \(n\) Eingabezahlen, erhöhe \(C[x]\) um 1. (Jedes \(C[i]\) speichert jetzt, wie oft der Wert \(i\) unter den Eingabezahlen vorkommt.)
3. Transformiere \(C\) in ein Prefix-Summen-Array. \(C[i]\) speichert nun die Anzahl der Elemente kleiner oder gleich \(i\).

Pseudocode:

plaintext
Vorverarbeitung(A, k):
1. C = Array der Länge k+1 mit Werten 0
2. für jedes Element x in A:
       C[x] += 1
3. für i von 1 bis k:
       C[i] += C[i-1]

Dieser Vorverarbeitungsschritt fällt unter \(O(n + k)\), da das erste Durchlaufen und Zählen \(O(n)\) und das Bilden der kumulativen Summen \(O(k)\) dauert.

Anfragen (anzahl(a, b)):

Nach dem Vorverarbeitungsschritt kannst du die Anzahl der Zahlen im Bereich \([a, b]\) durch Abziehen der Präfixsumme bis \(a-1\) von der Präfixsumme bis \(b\) berechnen. Wenn \(a = 0\), beachte, dass keine Elemente kleiner als \(0\) existieren und daher \(C[-1]\) als \(0\) betrachtet wird.

Pseudocode:

plaintext
anzahl(a, b):
    if a > 0:
        return C[b] - C[a-1]
    else:
        return C[b]

Diese Methode ermöglicht es, die Anzahl der Elemente im Bereich \([a, b]\) in konstanter Zeit \(O(1)\) zu bestimmen, nachdem die Vorverarbeitung abgeschlossen ist. Die Prüfung auf \(a > 0\) dient der korrekten Handhabung des Falles, dass \(a\) am unteren Ende des Bereichs liegt.

Dein ursprünglicher Ansatz, jede Anfrage direkt zu durchlaufen, würde nicht die konstante Anfragezeit erfüllen. Mit dieser korrigierten Vorgehensweise von kumulativen Summen (Präfixsummen) erreichst du die gestellten Anforderungen.