Metody Programowania - Lista 9

Zadanie 1

Obliczyć dokładnie (jako funkcję n) ilość porównań (tzn. znaleźć wzór) w algorytmie sortowania przez wybór:

void sortuj(int * ll, int n)
{
        int i, mi, tmp;
        for(i = 0; < n - 1; i++) {
                int k;
                mi = i;
                for(k = i + 1; k < n; k++) {
                        if(ll[k] < ll[mi]) mi = k;
                }
                tmp = ll[i];
                ll[i] = ll[mi];
                ll[mi] = tmp;
        }
}

Sprawdzić wynik modyfikując program tak by obliczył i wypisał ilość porównań.

Zadanie 2

a) Obliczyć ilości działań arytnetycznych potrzebnych do obliczenia wartości wielomianu stopnia n różnymi metodami (sumowanie wyrazów z obliczaniem potęg oddzielnie dla każdego wyrazu (przy pomocy oddzielnej funkcji), przy iteracyjnym obliczaniu potęg (równocześnie z obliczaniem sumy), itp.). Przedyskutowac wyniki.

b) Obliczyć ilości działań arytnetycznych potrzebnych do pomnożenia dwu macierzy n na n metodą "z definicji".

Zadanie 3

Zapisać w prostszej postaci: O(2n^5-3n^2+17), O((7n^4+5n^2-48)/(n^2+24)), O(n^2*log(3n^5+21*n^2+6)). Uwaga: Znak '^' oznacza tu potęgowanie.

Zadanie 4

Zapisać w notacji asymptotycznej (O) ilości operacji w problemach z zadań 1 i 2.

Zadanie 5

Zaprogramować jako procedurę podane na wykładzie algorytmy wyszukiwania podciągu o maksymalnej sumie. Napisać program główny który wyprodukuje ciąg losowy o zadanej długości. Zmierzyć zależność czasu wykonania programu od długości ciągu - najpierw użyć polecenia time, a później programu gprof. Co zrobić żeby w mierę dokładnie oszacować czas wykonania naszej procedury?