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 θ(n3)
Jest w ktoś stanie pomóc?
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 θ(n3)
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ć 83 na 43? 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
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
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
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) = 2n-2.
w(n+1) = w(0) + ... +w(n) = 0 + 1 +1 + 2 + ... + 2n-2 = 2n-1.