[C++] Złożoność czasowa

Odpowiedz Nowy wątek
2011-10-18 10:18
0

Witam,
Czy może ktoś sprawdzić czy dobrze wyznaczam złożoność czasową tej procedury?
Z góry dziękuję.
Pozdrawiam

int kwadrat(int tabliczka[n])
{
    vector<int> tablica;
    n=sizeof(tabliczka);

    for(int i=0; i<1/4*n; i++)
    {
        tablica[i].pushback(tabliczka[i]);
    }

    kwadrat(tablica);

    for(int i=1/4*n; n<1/2n; i++)
    {
        tablica[i]=tabliczka[i]
    }
    kwadrat(tablica);

    for(int i=3/4*n; i<n; i++)
    {
        tablica[i]=tabliczka[i]
    }
    kwadrat(tablica);
}

złożoność czasowa
T(n)=3T(n/4)+3(n/4)
theta(n^(log(_4)3)*log n)

edytowany 1x, ostatnio: matti2515, 2011-10-18 10:39

Pozostało 580 znaków

2011-10-18 13:35
0

A to się kompiluje? tablica[i].pushback(tabliczka[i]) powinno wywalać błąd wg mnie. No i kolejne przypisania, tzn w następnych pętlach odwołują się do niezaalokowanej pamięci.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
metoda nic nie zwraca, a ma zwrócić int... myślę, że chodzi raczej o sam algorytm, a nie szczegóły implementacyjne - ŁF 2011-10-18 14:00

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