Złożoność algorytmu

Odpowiedz Nowy wątek
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
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
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
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

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
Liczba odpowiedzi na stronę

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