Znalezienie czasu pracy programu - c ++, wydajność, algorytm

Jestem nowy w Algorithms i DS. Mam na myśli książkę i mam kilka pytań, które mam trudności ze zrozumieniem.

Muszę znaleźć czas trwania następujących programów: (komentarze pochodzą tylko z książki)

function(int n) {
for(int i=1;i<=n/3;i++) { // will execute n/3 time
for(int j=1;j<=n;j+=4) { // will execute n/4 times
printf("*");
}
}
}

Odpowiedź: O (n ^ 2)

Jak to jest n ^ 2? Pierwsza pętla zostanie wykonana dla n / 3 razy, a druga dla n / 4. n / 3 * n / 4 = n ^ 2/12. Jak to jest n ^ 2? Proszę, pomóż mi zrozumieć.

pytanie 2

function(int n) {
for(int i=0;i<n;i++) { // will execute n times
for(int j=i;j<i*i;j+=4) { // will execute n*n times ?????? (How?)
if(j%i==0) {
for(int k=0;k<j;k++) { // will execute j times
printf("*");
}
}
}
}
}

Odpowiedź: O (n ^ 5)

Pierwsza pętla jest wykonywana n razy. W porządku.

Jak wykonuje się drugą pętlę dla n * n razy? Tutaj wartość j jest inicjalizowana do i, więc nie powinno być (n * n) -i razy? Jeśli j było zainicjowane na 0, byłby to n * n razy, prawda?

Trzecia pętla wykonuje j razy, ponieważ k

Proszę mi pomóc zrozumieć, dlaczego druga pętla (j) zostanie wykonana n * n razy. Dziękuję Ci.

Odpowiedzi:

0 dla odpowiedzi № 1

Książka zajmuje się big-Oh. Kompletne wprowadzenie do big-Oh byłoby zbyt długie, ale w big-Oh-land utrzymuje, że:

O(a*f(n)) = O(f(n))

z a stała.

innym jest to, że:

O(a_k * n^k+ a_(k-1) n^(k-1)+...+a_0) = O(n^k)

z f(n) funkcja losowa.

---

O Drugie Pytanie: druga pętla biegnie od i do i*i. Teraz od i dosięgnie n-1 ma rozmiar O(n), więc pętla zostanie wykonana w ostatnim przebiegu (n-1)*(n-1) czasy. Od j ostatecznie dotrze do czegoś w kolejności O(n^2) i trzecia pętla biegnie od 0 do j-1, trzecia (najbardziej wewnętrzna) pętla ma złożoność czasu O(n^2) także. Oznacza to, że całkowita złożoność czasu pętli wynosi:

O(n)*O(n^2)*O(n^2)=O(n^5)

---