Badanie efektywności algorytmów pseudowielomianowych - omówienie

Wrocław,
Struktury danych i złożoność obliczeniowa.
Projekt 2
Temat: Badanie efektywności algorytmów pseudowielomianowych.
1. Cele.
Implementacja optymalnego algorytmu rozwiązującego binarny problem plecakowy i zbadanie czasów jego działania dla różnych parametrów
2. Informacje dotyczące języka oraz sprzętu na którym wykonywany jest eksperyment.
Program został napisany w języku C++ oraz skompilowany w kompilatorze DevC++. Doświadczenie wykonaliśmy na komputerze z procesorem Pentium Dual-Core T4300 2x2.10 GHz. Komputer posiada 3GHz pamięci RAM.
3. Opracowanie wyników pomiarów.
3. 1. W zależności od zmieniającej się liczby elementów.
Rysunek 1
Z powyższego wykresu wynika, że czas wykonywania algorytmu rośnie wraz ze wzrostem liczby elementów w sposób liniowy. Wykresy oczywiście różnią się od siebie tempem wzrostu oraz punktem początkowym. Wynika to z objętości plecaka. Im większy plecak tym początkowy czas wykonywania jest większy, tak samo jak tempo wzrostu.
3. 2. W zależności od rozmiaru plecaka.
Rysunek 2
Z kolei ten wykres przedstawia czasy działania w zależności od rozmiaru plecaka. Możemy zauważyć, że tempo wzrostu czasu działania jest mniejsze niż w przypadku wykresu 1 (Rys. 1). Tak jak powyżej wykresy różnią się czasem początkowym, który w tym przypadku wynika z liczby elementów. Ma ona również wpływ na tempo wzrostu czasu działania. 4. Tabele pomiarowe.
j
B
T[ms]
1000
1000
31
1000
1000
28
1000
1000
19
1000
1000
20
1000
1000
31
średnia
26
2000
1000
67
2000
1000
49
2000
1000
65
2000
1000
45
2000
1000
64
średnia
58
3000
1000
116
3000
1000
54
3000
1000
135
3000
1000
151
3000
1000
71
średnia
105
4000
1000
291
4000
1000
185
4000
1000
192
4000
1000
74
4000
1000
84

(…)

…++ oraz skompilowany w kompilatorze DevC++. Doświadczenie wykonaliśmy na komputerze z procesorem Pentium Dual-Core T4300 2x2.10 GHz. Komputer posiada 3GHz pamięci RAM.
3. Opracowanie wyników pomiarów.
3. 1. W zależności od zmieniającej się liczby elementów.
Rysunek 1
Z powyższego wykresu wynika, że czas wykonywania algorytmu rośnie wraz ze wzrostem liczby elementów w sposób liniowy. Wykresy oczywiście różnią…
... zobacz całą notatkę