80879 zdj5 (3)
Twierdzenie: Każde drzewo decyzyjne,
odpowiadające algorytmowi poprawnie sortującemu n elementów, ma wysokość D(n lg2n).
Dowód
Liczba permutacji n elementów wynosi n!
Drzewo o wysokości h nie może mieć więcej niż 2h liści
n! < 2h h > lg2 (n!)
nf = (n/e) n e = 2.71828... h > Ig2 (n/e) n = n lg2 n-n lg2e = Q (n lg2 n)
Wvkład 11 Prosj amowame komputerów I 38
Wyszukiwarka
Podobne podstrony:
24751 zdj5 Programowanie dynamiczne Użycie strategii programowania dynamicznego polega na zapamięta
zdj cie202 30 Zastosowania actio Paułiann: - odpowiedzialność za działania na szkodę
Instrukcja obslugi COLT CZ5 5 Fntrłt lywli^rwutw lite* odpowiednią petycję fotela, a następnie wep
1.2 Twierdzenie Biichiego Pokażemy, że odpowiednią logiką do opisywania języków regularnych jest log
badanych nie wybrałoby tego kierunku ponownie, a prawie 30% twierdzi, że studia nie odpowiadają ich
21550 zdj5 Prosty Problem Przydziału 4+5+11 + 14 = 34 F 4 6 3 34+1-4 =
więcej podobnych podstron