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
średnia		165
5000	1000	250
5000	1000	249
5000	1000	272
5000	1000	239
5000	1000	84
średnia		219
1000	2000	41
1000	2000	35
1000	2000	41
1000	2000	42
1000	2000	41
średnia		40
2000	2000	93
2000	2000	94
2000	2000	102
2000	2000	94
2000	2000	94
średnia		95
3000	2000	159
3000	2000	158
3000	2000	103
3000	2000	104
3000	2000	103
średnia		125
4000	2000	237
4000	2000	237
4000	2000	238
4000	2000	237
4000	2000	234
średnia		237
5000	2000	328
5000	2000	331
5000	2000	330
5000	2000	328
5000	2000	172
średnia		298
1000	3000	53
1000	3000	58
1000	3000	59
1000	3000	59
1000	3000	59
średnia		58
2000	3000	105
2000	3000	130
2000	3000	130
2000	3000	105
2000	3000	130
średnia		120
3000	3000	159
3000	3000	214
3000	3000	158
3000	3000	214
3000	3000	214
średnia		192
4000	3000	209
4000	3000	316
4000	3000	212
4000	3000	213
4000	3000	310
średnia		252
5000	3000	418
5000	3000	419
5000	3000	263
5000	3000	417
5000	3000	261
średnia		356
1000	4000	77
1000	4000	86
1000	4000	78
1000	4000	77
1000	4000	77
średnia		79
2000	4000	166
2000	4000	141
2000	4000	139
2000	4000	167
2000	4000	168
średnia		156
3000	4000	273
3000	4000	268
3000	4000	212
3000	4000	208
3000	4000	262
średnia		245
4000	4000	283
4000	4000	380
4000	4000	380
4000	4000	380
4000	4000	380
średnia		361
5000	4000	350
5000	4000	503
5000	4000	504
5000	4000	347
5000	4000	504
średnia		442
1000	5000	96
1000	5000	94
1000	5000	89
1000	5000	95
1000	5000	94
średnia		94
2000	5000	199
2000	5000	199
2000	5000	201
2000	5000	200
2000	5000	201
średnia		200
3000	5000	319
3000	5000	320
3000	5000	261
3000	5000	262
3000	5000	319
średnia		296
4000	5000	350
4000	5000	450
4000	5000	449
4000	5000	449
4000	5000	349
średnia		409
5000	5000	437
5000	5000	598
5000	5000	613
5000	5000	597
5000	5000	459
średnia		541

Tabela 1Wyniki pomiarów

j	B	t
1000	1000	26
2000	1000	58
3000	1000	105
4000	1000	165
5000	1000	219
1000	2000	40
2000	2000	95
3000	2000	125
4000	2000	237
5000	2000	298
1000	3000	58
2000	3000	120
3000	3000	192
4000	3000	252
5000	3000	356
1000	4000	79
2000	4000	156
3000	4000	245
4000	4000	361
5000	4000	442
1000	5000	94
2000	5000	200
3000	5000	296
4000	5000	409
5000	5000	541

Tabela 2 Uśrednione wyniki

5. 4. Wnioski ogólne.

Algorytm jest zależny zarówno od liczby elementów, jak i rozmiaru plecaka. Jednak największy wpływ na szybkość wykonywania ma liczba elementów.

Dla małej liczby elementów wzrost rozmiaru plecaka ma minimalny wpływ na przyrost czasu wykonywania, natomiast w przypadku dużej liczby elementów wzrost ten jest już znaczniejszy.

- 1 -

---