Informatiker Board | Druckvorschau: Master-Theorem

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Master-Theorem (http://www.informatikerboard.de/board/thread.php?threadid=1871)

Geschrieben von MarioH am 19.06.2014 um 08:59:

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: