Złożoność algorytmu

Odpowiedz Nowy wątek
Zimny Orzeł
2015-01-09 10:59
Zimny Orzeł
0

Jaka jest złożoność takiego algorytmu? Niestety nie wystarczy powiedzieć, że jest złożoność O() tylko dokładnie T(n), np. T(n)=2nlgn + 4n. Nie wiem jak przeprowadzić analizę bo jak wybrać czynność elementarną? Jak zestawić równanie logiczne jakasWartos ze wstawieniem do wektora. Bardzo proszę o pomoc

jakasWartos to wyrażenie logiczne np. a*4 < 3- b

int func()
{
    wektor.push_back(jakasWartosc1);                    

        // wykonuje się tyle razy ile trójkątów
    for(int i=0; i<n; i++)
    {    
        if( jakisWarunek1 )
            break;

        if(jakisWarunek2 && jakisWarunek3)
            treeBST.insert(cos);          // wstawienie do drzewa BST  - złożoność O(lgn)

        if((jakisWarunek4 && jakisWarunek5 && jakisWarunek6)
        {
            wektor.push_back( jakasWartosc);
            if(    jakisWarunek7)
                wektor.push_back(jakasWartosc);    
            else
                wektor.push_back(jakasWartosc);
        }
    }

    wektor.push_back( jakisPunkt );

    Node * m;
    if(jakisWarunek8)
    {
        m = treeBST.minNode();   // element o najmniejszym kluczu w drzewie BST
        if(jakisWarunek9 && jakisWarunek10 )
            wektor.pop_back();

        for(int i=0; i<n; i++)
        {
            if(jakisWarunek11)
                break;

            if(jakisWarunek12) 
            {
                int x, y;
                if(warunek13)
                {x = 4; y =1;}
                else
                {x = 3; y =2;}

                if(jakisWarunek14)
                {
                    wektor.push_back( jakasWartosc);
                    wektor.push_back( jakasWartosc);
                }
                if(jakisWarunek15)
                {
                    wektor.push_back( jakasWartosc );
                    wektor.push_back( jakasWartosc );
                }
            }

            m = drzewoBST.successor(m);                             // zwraca następnik n w drzewie BST
        }
    }
}
edytowany 1x, ostatnio: somekind, 2016-12-13 18:26
Na przyszłość sam wstawiaj kod w znaczniki. - somekind 2015-01-09 12:20

Pozostało 580 znaków

2015-01-09 12:57
Moderator

Rejestracja: 16 lat temu

Ostatnio: 3 godziny temu

0

"Dokładnie" to się nie da, bo nie wiadomo jak kosztowne są operacje elementarne. Poza tym nie napisałeś nawet czy chodzi o przypadek optymistyczny, średni czy pesymistyczny ;]


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

Pozostało 580 znaków

2015-01-09 13:03

Rejestracja: 5 lat temu

Ostatnio: 4 lata temu

0

a jak w złożonosci algorytmu jest napisane : "czyli program działa w czasie O ( N )." to co to oznacza? :D

Pozostało 580 znaków

2015-01-09 13:34
Moderator

Rejestracja: 16 lat temu

Ostatnio: 3 godziny temu

0

To znaczy że górne ograniczenie na czas działania algorytmu jest liniowe względem rozmiaru danych wejściowych.


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

Pozostało 580 znaków

Zimny Orzeł
2015-01-09 13:36
Zimny Orzeł
0

chodzi o gorne ograniczenie O(T(n))

Ogólnie jezeli dobrze mysle to należy do klasy O(nlg).

Pozostało 580 znaków

Odpowiedz

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