Pro následující třídicí algoritmus na následujících daných vstupních datech ověřte
jeho chování a spočítejte počet porovnání a počet volání funkce swap:
1 procedure bubblesort (A[1..n])
2 for i := 1 to n - 1 do
3 for j := 1 to n - i do
4 if A[j] > A[j+1] then
5 swap A[j], A[j+1]
a) A = [5, 3, 1, 6]
b) A = [2, 3, 7, 9]
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 daty jsou již setřízené posloupnosti).
Rozhodněte, zda jsou následující tvrzení pravdivá nebo nepravdivá:
f(n) = 3n5
− 16n + 2
a) f ∈ O(n5
)
b) f ∈ O(n)
c) f ∈ O(n17
)
d) f ∈ Ω(n5
)
e) f ∈ Θ(n5
)
f) f ∈ Θ(n)
g) f ∈ Θ(n17
)
Pro následující funkce f a g nakreslete jejich graf a určete dvojici konstant c a n0,
která je svědkem toho, že platí f ∈ O(g), resp. g ∈ Ω(f). Kolik existuje takových
dvojic?
a) f(n) = 1
2n + 5; g(n) = n2
− 4n + 7
b) f(n) = log2 n; g(n) = 2n−1
− 2
Dokažte, že platí následující tvrzení:
1. log n ∈ O(n)
2. 2n+1
∈ O(3n
n )
Seřaďte následující funkce podle rychlosti jejich růstu:
n2
+ log n 7n5
− n3
+ n n2
log log n 2n
log n
(3
2)n
n · log n n!
n nn
6
log(n!) log14
n
Pro exaktní řešení problému obchodního cestujícího je znám algoritmus v O(2n
)
(závislost na počtu měst). 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.
Určete časovou složitost následujících algoritmů vzhledem k velikosti n:
1 procedure printer1 (A[1..n])
2 for i := 1 to 100000 do
3 if i < n then print A[i]
1 procedure printer2 (A[1..n])
2 for i := 1 to n - 1 do
3 for j := i to i + 1 do
4 print A[j]
1 procedure bubblesort (A[1..n])
2 for i := 1 to n - 1 do
3 for j := 1 to n - i do
4 if A[j] > A[j+1] then
5 swap A[j], A[j+1]
Určete časovou složitost následujícího algoritmu, který vrátí součin dvou přirozených
čísel y a z.
1 function multiply (y, z)
2 x := 0
3 while z > 0 do
4 if z is odd then x := x + y
5 y := 2 * y
6 z := z
2
7 return x
Co počítají následující dvě funkce? Jaká je jejich složitost?
1 function kralicek(n: integer)
2 if n < 0 then fail "Chyba"
3 if n < 2
4 then return n
5 else
6 return kralicek(n-1) + kralicek(n-2)
1 function mysicka(n: integer)
2 if n < 0 then fail "Chyba"
3 first := 0
4 second := 1
5 for i := 1 to n do
6 (first,secod)
7 := (second,first+second)
8 return first
Tabulka časů výpočtu algoritmů o složitostech log n, 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
log n 0,000001s 0,000001s 0,000002s 0,000003s
n 0,00001s 0,00002s 0,00005s 0,001s
n2
0,0001s 0,0004s 0,0025s 1s
2n
0,001024s 1,048576s 35,7 let 3, 4 · 10287
let*
nn
2,8 hodiny 3 · 1012
let*
* Stáří vesmíru je odhadováno na 13, 7.109
let.