[Teoria złożoności] Asymptotyczna pesymistyczna złożoność

Odpowiedz Nowy wątek
2015-02-18 09:52
0

Mam dany kod:

        wstaw( int n,int*t)
        {
            int v[ 100];
            int i, j, k;
            for (i = 0; i < 100; i++)
                v[i] = 0;
            for (i = 0; i < n; i++)
                v[t[i] % 100]++;
            j = 0;
            k = 0;
            while (j < n) {
                while (v[k]-- > 0)
                    t[j++] = k;
                k++;
            }
        }

Jego zadaniem jest wstawianie liczb całkowitych dodatnich zapisanych w tablicy t[n] niemalejąco względem reszty z dzielenia przez 100.
Mam obliczyć asymptotyczną pesymistyczną złożoność algorytmu tablicy o 12 elementach. Proszę o pomoc

edytowany 2x, ostatnio: Shalom, 2015-02-18 10:04

Pozostało 580 znaków

2015-02-18 10:39
0

Nie ma czegoś takiego jak asymptotyczna złożoność dla danych o konkretnym rozmiarze. Dla danych o 100 elementach ten algorytm zawsze będzie O(1) bo nie ma tam elementu zmiennego! Ale ok załóżmy że rozmiar danych to k. Jak widać masz pętlę i k przejściach a potem dwie pętle while. Niby to dwie zagnieżdżone pętle, ale wiemy że tablica v ma sumarycznie k elementów, biorąc pod uwagę jak ją tworzono. W efekcie te dwie pętle while w sumie wykonaja sie k razy. W efekcie złożoność to O(k).


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0