lA Pro následující třídicí algoritmus na následujících vstupních datech ověřte jeho
chování a spočtěte počet volání funkce swap a počet porovnání:
procedure bubblesort (A[l..n])
1. for i := 1 to n - 1 do
2. for j := 1 to n - i do
3. if A [j] > A[j + 1] then
4. swap A [j] , A[j+1] ;
a) A = [5,3,1,6] b) A = [2,3,7,9]
2A Rozhodněte, zda jsou následující tvrzení pravdivá nebo nepravdivá:
a. 3 n 5
- 1 6 n + 2 G 0{rr)
b. 3n5
- 16n + 2 G o\n)
c. 3n5
- 16n + 2 G 0(n17
)
d. 3 n 5
- 16n + 2 e í}(n5
)
e. 3n5
- 16n + 2 G 6(n5
)
f. 3n5
- 16n + 2 G Q (n)
g. 3n5
- 16n + 2 G 6(n17
)
3 A Dokažte, že platí následující tvrzení:
1. log n  0{n
n
2. 2n + i
G 0(*v
n
4A Seřaďte následující funkce podle ryc
n2
+ log n 7n5
-- n3
+ n
log log n 2n
(|)n
n log n
n nn
n! n2
6 log n
log n! log14
n
osti jejich růstu:
5 A Pro exaktní řešení problému obchodního cestujícího je znám algoritmus v 0(2n
).
Při jeho řešení na starém počítači trval výpočet pro 36 měst téměř jeden den. Nyní
máme k dispozici nový počítač, který je 1000-krát rychlejší. Určete, kolik měst můžeme
zpracovat, aby výpočet nepřesáhl jeden den.
6 Á Určete časovou složitost následujícího algoritmu:
procedure bubblesort (A[l..n])
1. for i := 1 to n - 1 do
2. for j := 1 to n - i do
3. if A [j] > A[j + 1] then
4. swap A [j] , A[j+1] ;
7A Zkuste modifikovat algoritmus bubblesort tak, aby se zlepšila jeho složitost na
příznivých datech (nápověda: nejvíce příznivými data jsou již setřízené posloupnosti).
8A Určete časovou složitost následujícího algoritmu, který vrátí součin dvou
přirozených čísel y a z.
function multiply (y, z)
1. x := 0;
2. while z > 0 do
3. if z is odd then x := x + y;
4. y := 2y;
o. z : -- |_2J >
6. return (x);
9 A Určete časovou složitost algoritmu lineárního vyhledávání pro vyhledání klíče (vrací
index nalezeného prvku v poli D)
function Is (n, k: Int, D:array[Int] of Int): Int;
{ n je pocet prvku v poli D, k je hledaný klič}
var index: Int;
1. index := -1;
2. for i := 1 to n do
3. if k = D[i] then index := i;
4. if (index = -1) then "prvek nenalezen"
5. else return(index);
IOÁ Určete časovou složitost algoritmu binárního vyhledávání pro vyhledání klíče v
setřízeném poli D
D: array[Int] of Int;
function bs (1, r, k: Int ): Int
{ 1, r jsou levý a pravý konec pole D, k je hledaný klíč }
var m, index: Integer;
1. if 1 > r then return(-l) {nenalezeno}
else begin
2. m := (1 + r) div 2;
3. if k < D[m] then return(bs(l, m-1, k))
4. else if k > D[m] then return (bs(m+l, r, k))
5. else return(m);
end
H A U následujících dvou algoritmů počítajících mocninu čísla určete jejich časovou
složitost.
function powerl (z, n) {Předpokládá se z > 0, n > 0 }
1. r := 1;
2. for i := 1 to n do
3. r := r * z;
4. return(r);
function power2 (z, n)
1. r := 1;
3. if n = 0 then return(l);
4. while n > 0 do
4. if n is odd then
6. r := r * t;
7. n := n div 2;
8. t := t * t;
endwhile
9. return(r);
12A Tabulka časů výpočtu algoritmů o složitostech logn, n, n2
, 2n
a nn
pro vstup
délky 10, 20, 50 a 1000. Předpokládejme, že jedna iterace algoritmu trvá 1/ÍS.
10 20 50 1000
logn 0,000001s 0,000001s 0,000002s 0,000003s
n 0,00001s 0,00002s 0,00005s 0,001s
2
0,0001s 0,0004s 0,0025s ls
2n
0,001024s l,048576s 35,7 let 3,4-10287
let*
n11
2,8 hodiny 3 ˇ 1012
let*
* Stáří vesmíru je odhadováno na 13, 7.109
let.