Złożoność obliczeniowa programu


(arek199602) #1

Witam czy ktoś mógłby mi powiedzieć  jak najprościej określić złożoność obliczeniową mojego kodu ?

// algorytm ma być liniowy
#include <iostream>
void wypisz_tab (bool [][100]);
void znajdz_idola (bool [][100],int);
int main()
{
    std::cout<< "Podaj liczbe osob na przyjeciu.\n";
    int liczba_osob;
    std::cin>>liczba_osob;
    std::cout<< "Podaj liczbe znajomosci.\n";
    int liczba_znajomosci;
    std::cin>>liczba_znajomosci;
    bool znajomosci[100][100] {};
    std::cout<< "Podaj znajomosci.\n";
    for (int i=0;i<liczba_znajomosci;i++)
    {
        int x,y;
        std::cout<< "Podaj x\n";
        std::cin>>x;
        std::cout<< "Podaj y\n";
        std::cin>>y;
        znajomosci[x][y]=true;
    }
    znajdz_idola(znajomosci,liczba_osob);

    //wypisz_tab(znajomosci);

}
void wypisz_tab (bool tab [][100])
{
    for (int i=0;i<6;i++)
    {
        for (int j=0;j<6;j++)
            std::cout<<tab[i][j]<< " ";
        std::cout<< "\n";
    }
}
void znajdz_idola (bool tab [][100],int Size)
{
    int idol=0,ile=0;
    for (int i=0;i<Size;i++)
    {
        for (int j=1;j<Size;j++)
        {
             if (tab[i][j]==true)
             {
                idol++;
                ile++;
                break;
             }
        }
        if (ile==0)
            break;
        ile=0;

    }
    ile=0;
    int j;
        for ( j=0;j<Size;j++)
        {
            if (j==idol)
                continue;
            if (tab[j][idol]==false)
            {
                std::cout<< "Nie ma idola.\n";
                ile++;
                break;
            }
        }
        if (j==Size)
            std::cout<< "Idolem jest "<<idol;



}

 


(Longhorn2009) #2

Wygląda na złożoność liniową O(n) w notacji omikron, choć mogę sie mylić, programistą nie jestem ツ


(Johny) #3

Każda funkcja oddzielnie.

2 pętle for to O(n^2)=O(n*n).

Pojedyncza pętla for to O(n).

Pod tym kątem musisz przeanalizować cały program i potem pododawać złożoności.

 


(arek199602) #4

ok dzięki za pomoc