Złożoność algorytmów

Odpowiedz Nowy wątek
2016-01-05 21:24
Złoty Mleczarz
0

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?

edytowany 1x, ostatnio: Shalom, 2016-12-13 18:26
dla tak małych n raczej każde oszacowanie bierze w łeb. - _13th_Dragon 2016-01-05 21:47

Pozostało 580 znaków

2016-01-05 21:46
2

0,002
0,008


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2016-01-06 11:09
Biały Szczur
1

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

Pozostało 580 znaków

2016-01-06 11:12
0
θ(4) = 0.001
θ(8) = ?
θ(4^3) = 0.001
θ(8^3) = ?

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

Pozostało 580 znaków

2016-01-06 11:30
Biały Szczur
0

Fkatycznie, w podpunkcie a) wystarczy pomnożyć 0,001 * 2, a w podpunkcie b) podzielić 83 na 43? Wtedy to daje 2

Pozostało 580 znaków

2016-01-06 11:44
Biały Szczur
0

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ć?

Pozostało 580 znaków

2016-01-06 12:02
0

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

Szacuje się, że w Polsce brakuje 50 tys. programistów
edytowany 3x, ostatnio: vpiotr, 2016-01-06 12:05
Prościej napisać że dla małych n - bez sensu - _13th_Dragon 2016-01-06 19:12

Pozostało 580 znaków

2016-01-06 12:04
Biały Szczur
0

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

Pozostało 580 znaków

2016-01-06 16:10
2

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.


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell
edytowany 1x, ostatnio: bogdans, 2016-01-06 16:12

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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