+1 Daumen
788 Aufrufe

Aufgabe:

Sei \( \alpha \in \mathbb{N}_{\geq 0} \) eine Konstante. Zeigen Sie, dass man ein Feld der Länge \( n \) mit Zahlen aus dem Wertebereich \( \left\{0, \ldots, n^{\alpha}\right\} \) mittels Radixsort in Zeit \( \mathcal{O}(n) \) sortieren kann.

Gehen Sie wie folgt vor:

1. Überlegen Sie sich, welche die kleinste und welche die größte \( b \)-adische Zahl ist, die Sie mit einer Basis \( b \in \mathbb{N}_{>0} \) und einer Ziffernanzahl \( d \in \mathbb{N}_{>0} \) erhalten können, indem Sie per Induktion zeigen, dass \( \sum \limits_{i=0}^{d-1} b^{i}=\frac{b^{d}-1}{b-1} \) gilt.


Kann mir jemand bitte helfen? :)

Avatar von

1 Antwort

0 Daumen

Zeig doch mal den Induktionsanfang für d=1, wie würdest du das machen?

Anschließend musst du zeigen wenn

$$ \sum \limits_{i=0}^{d-1} b^{i}=\frac{b^{d}-1}{b-1} $$

dann gilt auch

$$ \sum \limits_{i=0}^{(d+1)-1} b^{i}=\frac{b^{d+1}-1}{b-1} $$

Versuche mal von der zweiten Summe so Summanden abzuspalten, dass du die erste Gleichung einsetzen kannst.

Avatar von 6,0 k

Vielen Dank, das hilft mir. Jedoch verstehe ich eine Sache immer wenn mir etwas komplett vor Augen geführt wird und ich das so Schritt für Schritt durchgehe. Könntest du mir den Beweis komplett aufschreiben und ich sage dir dann was noch unklar ist (falls etwas unklar ist)? Das wäre sehr lieb.


:)

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community