Master-Theorem

19.06.2014, 08:59

MarioH

Master-Theorem

Meine Frage:
Berechnen Sie mit dem Master-Theorem die Komplexität der beiden Varianten unter der Annahme, dass die Parameterübergabe per Referenz eine Zeit in 119874(1) benötigt, während die Übergabe per Wert in 119874(119873) ist, wobei N die Anzahl der kopierten Arrayelemente darstellt.
Hinweis: Die Komplexität ist für beide Varianten verschieden.

Variante 1:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

def binarySearch(a, key, start, end): 
	size = end - start
	if size <= 0: 
		return None 
	center = (start + end) / 2
	if key == a[center]:  
		return center 
	elif key <  a[center]:  
		return binarySearch(a, key, start, center) 
	else: 
		return binarySearch(a, key, center+1, end)

Variante 2:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

def binarySearch2(a, key): 
	if len(a) == 0:  
		return None 
	center = len(a) / 2 
	if key == a[center]: 
		return center 
	elif key <  a[center]:  
		return binarySearch2(a[:center], key) 
	else:  
		res = binarySearch2(a[center+1:], key) 
		if res is None:  
			return None 
		else: 
			return res + center + 1

Meine Ideen:
Variante 1:

T(n) = T(n/2) + K
=> O(n^[logb a] * (log n)^(k+1))
=> O(1 * (log n)^(k+1))
=> O((log n)^(k+1))
=> O((log n)^1)
=> O(log n)

Variante 2:

19.06.2014, 09:02

Auf diesen Beitrag antworten »

marioh

Da ich noch nicht angemeldet war konnte ich meinen Beitrag nichtmehr ändern:

Oben im Aufgabentext bedeuten die Zahlen erst O(1) und dann O(N).

Neue Frage »

Antworten »

Master-Theorem

Verwandte Themen