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;
}