Algorithmen und Datenstrukturen

Logarithmisches Kostenmaß

Annahme:
jedes Datenelement belegt Speicherplatz, der von seiner numerischen Größe logarithmisch abhängt
 
--> für Zahl n > 0 ist die # der Bits zur Darstellung von n gleich 
 
Größe der Eingabe = Summe der logarithmischen Größe der Eingabeelemente
 
z.B.
Zerlegung einer in Dualdarstellung gegeben Zahl in Primfaktoren

Diskussion