Oszacuj złożoność algorytmu.

Question

Cześć,

walczę z tematem "złożoności czasowej algorytmów".

Mogę Was prosić o wytłumaczenie dwóch poniższych przykładów?

1.

• i=0;
• wykonuj:
• j=i;
• wykonuj:
• j=j+1;
• dopóki (j<n);
• i=i+1;
• dopóki (i<n);

2.
• i=0;
• wykonuj:
• j=1;
• wykonuj:
• j=j*2;
• dopóki (j<n);
• i=i+1;
• dopóki (i<n);

Dziękuję za pomoc.

Answer 1

0. Chodzi o pętle prawda? Dwie pętle z takimi indeksami:

        int n=3;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                cout<<"( "<<i<<", "<<j<<" )";

            }
            cout<<endl;
        }

Program wypisał tablicę 3 * 3, czyli wykonał n*n obliczeń więc jest złożoność n*n czyli n^2.

1. Pętla ta często jest stosowana do układów liczb bez powtórzeń.

        int n=5;
        for(int i=0; i<n; i++)
        {
            for(int j=i; j<n; j++)
            {
                cout<<"( "<<i<<", "<<j<<" )";

            }
            cout<<endl;
        }

Widać, że jest to trójkąt o przyprostokątnych n. W przybliżeniu (albo i naczej: dla większych n) złożoność, czyli poniekąd liczba wygenerowanych elementów to n*n/2 - tak naprawdę troszkę więcej. Połowa tego co poprzednio nie? Można też zobaczyć ilość elementów inaczej i wtedy już widać, że prawie pasuje:

#include <iostream>
#include <cmath>
int main()
{

    int k=1;
    for(int n=1; n<20; n++)
    {
        for(int i=0; i<n; i++)
            for(int j=i; j<n; j++)
            {
                //cout<<k<<endl;
                k++;
            }

        cout<<"--> n = "<<n<<" ---> zlozonosc ---> "<<k<<" przewidywane --> "<<n*n/2<<endl;
        k=0;
    }


    return false;
}

2. Tu już trochę trudniej. Tworząc takie pętle korzystając z dwóch powyższych kodów można zauważyć, że nie jest to złożoność liniowa i potęgowa. Można to porównać do n*log(n) przemnożone razy jakaś stała:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{

    int k=1;
    for(int n=1; n<50; n++)
    {
        for(int i=0; i<n; i++)
            for(int j=1; j<n; j*=2)
            {
                //cout<<k<<endl;
                k++;
            }

        cout<<"--> n = "<<n<<" ---> to ---> "<<k<<" przewidywane --> "<<3.6*n*log10(n)<<endl;
        k=0;
    }

        int n=12;
        for(int i=0; i<n; i++)
        {
            for(int j=1; j<n; j+=2)
            {
                cout<<"( "<<i<<", "<<j<<" )";

            }
            cout<<endl;
        }

    return false;
}