Złożoność algorytmów

Dla n=4 pewien program wykonuje się 0,001 sekundy. Oszacuj ile czasu będzie się on wykonywał
dla n = 8?

a) złożoność czasowa programu to θ(n)
b) złożoność czasowa programu to θ(n³)

Jest w ktoś stanie pomóc?

0,002
0,008

Mógłbyś napisać jakieś obliczenia? Dzięki

θ(4) = 0.001
θ(8) = ?

θ(4^3) = 0.001
θ(8^3) = ?

oblicz sobie sam rownanie. Jest na poziomie podstawowki (no moze gimnazjum)

Fkatycznie, w podpunkcie a) wystarczy pomnożyć 0,001 * 2, a w podpunkcie b) podzielić 8^{3 na 4}3? Wtedy to daje 2

Jeszcze mam podpunkt c):

Kod programu ma postać (za złożoność przyjmij liczbę wywołań rekurencyjnych)

void program(int n)
{
if(n == 0)
return;
else
for(int i = 0; i < n; i++)
program(i);
}

Jak się za to zabrać?

Uwaga: oba zadania nie mają rozwiązania (a właściwie mają ich nieskończenie wiele) jeśli O(0) != 0.

Natomiast jeśli O(0) = 0, to

Rozwiązanie 1

O(n) = n * a
O(n1) = n1 * a = 0.001
O(n2) = n2 * a

n1 * a = 0.001
n1 = 4
a = 0.001 / 4
a = 0,00025

O(n2) = 0,00025 * 8 = 0,002

Rozwiązanie 2 A

O(n) = n^3 * a
O(n1) = n1^3 * a = 0.001

n1^3 * a = 0.001
a = 0.001 / (n1^3)
n1 = 4
a = 0.001 / (4^3) 
a = 0,000015625

O(n2) = 8^3 * 0,000015625 = 0,008

Rozwiązanie 2 B

O(n1) = n1^3 * a = 0.001
O(n2) = (2 * n1)^3 * a = x

Układ:

n1^3 * a = 0.001
(2 * n1)^3 * a = x

n1^3 * a = 0.001
(2^3 * n1^3) * a = x

n1^3 * a = 0.001
2^3 * (n1^3 * a) = x

n1^3 * a = 0.001
2^3 * 0.001 = x

x = 2^3 * 0.001 = 0.008

ok dzięki, a jak się zabrać za rekurencję?

Ilość wywołań oznaczam w(n).
Z lenistwa będę pisał p(n) zamiast program(n).
Dla n=0 nie ma żadnych wywołań => w(0)=0
dla n=1 jest jedno wywołanie => w(1) = 1,
p(2) = p(0) + p(1) => w(2) = w(0) + w(1) = 1,
p(3) = p(0) + p(1) +p(2) => w(3) = w(0) + w(1) + w(2) = 2
Indukcyjnie dowodzimy, że (dla n >= 3) w(n) = 2^n-2.
w(n+1) = w(0) + ... +w(n) = 0 + 1 +1 + 2 + ... + 2^n-2 = 2^n-1.