1-5

1. Wyjaśnij, co oznacza złożonośd obliczeniowa algorytmu, a co złożonośd obliczeniowa problemu.
Złożoność obliczeniowa algorytmów – ilość zasobów niezbędnych do wykonania algorytmu. Przez
zasoby rozumie się zwykle czas (złożoność czasowa) i zajętość pamięci operacyjnej (złożoność
pamięciowa).
Natomiast przez pojęcie złożoności obliczeniowej problemu rozumie się złożoność obliczeniową
najlepszego algorytmu rozwiązującego problem.
2. Uzasadnid, że problem generowania wszystkich ciągów skooczonych o długości 100 w alfabecie ,0, 1,
2, 3 ,4 ,5 ,6 ,7 ,8 ,9} jest trudny obliczeniowo.
takich ciągów jest 10
100
przy założeniu, że na jeden ciąg potrzeba 1 μs to 10
100
* 10
-6
= 10
94

sekund = 3 * 10^87 lat tyle generowało by te ciągi (zaokrągliłem to do tego, że 100 sekund =
0.000003 roku). A wiec problem ten jest trudny obliczeniowo, ze względu na czas potrzebny do
wykonania zadania.
3. Stosując algorytm sortowania pęcherzykowego posortowad ciąg: 34, 21, 17, 25, 11.
34, 21, 17, 25, 11
21, 17, 25, 11, 34
17, 21, 11, 25, 34
17, 11, 21, 25, 34
11, 17, 21, 25, 34

4. Stosując algorytm sortowania kubełkowego posortowad ciąg: 61, 22, 33, 12, 20.
wartość min: 12
wartość max: 61

61-12+1=50 //tyle kubełków będzie potrzebnych z indeksami od 12 do 61, co 1.
każdą liczbę zaczynając od lewej pakujemy do kubełka o indeksie = wartości tej liczby:
Q[61]=61
Q[22]=22
Q[33]=33
Q[12]=12
Q[20]=20

na koniec robimy konkatenacje wszystkich niepustych kolejek (kubełków) po kolei według
indeksów od najmniejszego.
5. Przepisad listę na tablicę. *Podana lista, i częściowo uzupełniona tablica z kolumnami NEXT i NAME+
Powiedzmy, że mam sobie jakąś listę:
5->3->6->10->1->NULL
Indeks NAME NEXT
0 - 1
1 5 2
2 3 3
3 6 4
4 10 5
5 1 0