Złożoność algorytmu - najmniejsza możliwa - Notacja dużego O

0

Witam,
Mam problem z określeniem złożoności obliczeniowej dwóch algorytmów(Notacja dużego O).
W przypadku prostych algorytmów jestem w stanie to wyliczyć. W tym przypadku nie widzę jako takiej zależności...

Pierwszy algorytm

int j=1;
for(i=0;j*j<=n;i++) {
    if(i>=n) {
        i=0;
        j++;
    }
}

Drugi algorytm

int j=1;
for(i=0;j<=n;i++) {
    if(i>=n*n) {
        i=0;j=j*2;
    }
}

Nie jestem pewien jak to obliczyć.
W przypadku pierwszego będzie to: O(n x sqrt(n))?

Proszę o pomoc.

1

W przypadku pierwszego, raczej oczywiste O(sqrt(n)). W drugim chyba O(2^n).

3

Na oko pierwszy kod można zapisać jako

for(int j=1;j*j<=n;++j){
    for(int i=0;i<n;++i){
    }
}

więc wychodzi sqrt(n) * n.

Drugi jako:

for(int j=1;j<=n;j*=2){
    for(int i=0;i<n*n;++i){
    }
}

Więc wychodzi n^3

0
  1. W przypadku pierwszego mi również wyszło sqrt(n) * n = n^(3/2), ale nie miałem takiej odpowiedzi.
    Dostępne były: sqrt(n), n, n^2, n^3, n^4, n^2*log(n). Więc w takim przypadku lepiej napisać sqrt(n) czy może n^2?

  2. W przypadku drugiego algorytmu może być: n*n*log(n)? - dodałem zdjęcie dla n=1000

title

2
BigQuantumMan napisał(a):
  1. W przypadku pierwszego mi również wyszło sqrt(n) * n = n^(3/2), ale nie miałem takiej odpowiedzi.
    Dostępne były: sqrt(n), n, n^2, n^3, n^4, n^2*log(n). Więc w takim przypadku lepiej napisać sqrt(n) czy może n^2?

  2. W przypadku drugiego algorytmu może być: n*n*log(n)? - dodałem zdjęcie dla n=1000

title

Drugą Twoja odpowiedź potwierdzam. Co do pierwszej, z zasady jeśli funkcja jest O(f(n)), oraz f(n) jest O(g(n)), to ta funkcja jest również g(n), więc w szczególności n^(3/2) jest również O(n^2), ale ciężko powiedzieć o co chodziło twórcy zadania.

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