złożoność pętli zagnieżdżonych
Próbuję obliczyć złożoność pętli for za pomocą notacji Big O. Zrobiłem to wcześniej w moich innych klasach, ale ta jest bardziej rygorystyczna niż inne, ponieważ dotyczy rzeczywistego algorytmu. Kod jest następujący:
for(i=n ; i>1 ; i/=2) //for any size n
{
for(j = 1; j < i; j++)
{
x+=a
}
}
i
for(i=1 ; i<=n;i++,x=1) //for any size n
{
for(j = 1; j <= i; j++)
{
for(k = 1; k <= j; x+=a,k*=a)
{
}
}
}
Przybyłem, że pierwsza pętla ma złożoność O (n), ponieważ przechodzi przez listę n razy. Jeśli chodzi o drugą pętlę, jestem trochę zagubiony! Dziękujemy za pomoc w analizie. Każda pętla znajduje się we własnej przestrzeni, nie są razem.