5. Kolokwium - [2000]

2000-05-31,12:00

Sprawdzian z Analizy Algorytmów Grupa A Zadanie 1 Algorytm sortowania szybkiego (Quicksort) w rekurencyjnej wersji realizowanej na jednoprocesorowej maszynie korzysta ze stosu, na którym zapamiętywane są zmienne lokalne i adresy powrotu. Jakiego rzędu jest maksymalna zajętość stosu dla wersji algorytmu przedstawionej .na ćwiczeniach? Dla jakich danych występuje taka zajętość? Czy da się poprawić ten wynik? Jeśli tak, to w jaki sposób to osiągnąć i jaka będzie wtedy maksymalna zajętość stosu ?

Zadanie 2 W tablicy A[0...n-1] zapisany jest pewien ciąg zer i jedynek (tzn. A[i]=0 lub A[i]=1). Dany jest następujący algorytm: procedure incr; begin i:=0; while (i
Jaki jest średni czas działania algorytmu w zależności od n, jeśli jako dominującą operacje przyjmiemy zmianę elementu tablicy A, a każdy ciąg zer i jedynek jest jednakowo prawdopodobny?

Zadanie 3 Rozwiązać równanie rekurencyjne, tzn. wyznaczyć T(n) jako funkcje n: ,n = 0 10 T(n)=  nT ( n − 1) + 3n! , n > 0