Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2017/18 / Einführung in die Programmierung / Material / Tafelanschrieb 11.01.18


Inhaltsbereich

Tafelanschrieb 11.01.18

Tafelanschrieb aus der Vorlesung am 11.01.18

Plain Text icon Tafel110118.txt — Plain Text, 1 KB

Dateiinhalt

Sortieren durch Auswaehlen:

Verdoppeln der Arraygroesse fuehrt

von     auf
64     150

783    2980
2980   11727
11727  47203


O(n^2) umfasst alle Terme (Funktionen), die durch irgendein festes
Vielfaches von n^2 fuer grosse n beschraenkt sind.

Also ist sogar 100000 * n^2 + 100000000000 n = O(n^2)



Ablauf der Merge Operation auf dem Beispiel der Folien. 

from = 12
to = 21
mid = 16
n = 10
a = {...,5,9,10,12,17,1,8,11,20,32,...}
         ^                      ^
	 from                   to

b = {0,0,0,0,0,0,0,0,0,0}
     ^
     j

i1   i2   j     b 
12   17   0     {.... }
12   18   1     {1,...}
13   18   2     {1,5,...}
13   19   3     {1,5,8,...}
...

Artikelaktionen


Funktionsleiste