9752256899

1.    a < c

Wówczas ^ < 1, więc szereg Yli=o (f )* jest zbieżny do pewnego m £ 1Z⁺. Stąd T(n) = bmn.

2.    a = c

Wówczas | = 1, więc X)i=o (§)* = k + 1 = 0(log_cra). Stąd T(n) = 0(ralog_cra).

3.    a > c

Wówczas § > 1, więc:

□

Interpretacja: Twierdzenie określa złożoność algorytmów opartych na strategii dziel i zwyciężaj, które:

•    redukują problem dla danych o rozmiarze n do rozwiązania tego problemu dla a zestawów danych, każdy o rozmiarze n/c.

•    wykonują kroki 1 i 3 schematu ogólnego w czasie liniowym.

10 Przykłady.

10.1 Sortowanie

Nasze przykłady rozpoczniemy od zaprezentowania dwóch strategii Dziel i Zwyciężaj dla problemu sortowania.

Problem:

Dane:    tablica T[l..n] elementów z uporządkowanego liniowo uniwersum

Zadanie:    uporządkować T 10.1.1 Strategia 1: Sortowanie przez scalanie.

Strategia ta oparta jest na tym, że dwa uporządkowane ciągi potrafimy szybko (w czasie liniowym) scalić w jeden ciąg. Aby posortować tablicę wystarczy więc podzielić ją na dwie części, niezależnie posortować każdą z części a następnie scalić je.

15

Wyszukiwarka

Podobne podstrony:
img055 (25) 60 . Ciąg iterowany zdefiniowany formułą rekurencyjną (3.67) algorytmu iteracji prostej
IMAG0165 (10) 1) Rozstrzygnąć, czy szereg    (- 4)n arctg A jest zbieżny bezwzględnie
68674 skanuj0041 (15) O szeregu, który jest.zbieżny, ale nie jest zbieżny bezwzględnie mówimy, że je
013 ZADANIA _ 1.    Sprawdź, czy szereg geometryczny jest zbieżny. Jeśli jest, to ob
2 (2256) Rozstrzygnąć, czy szereg (-1)" warcsin— jest zbieżny szwzględnie, czy warunkowo albo
74402 P241108 15 (2) H 1) Rozstrzygnąć, czy szereg ^ (-4)” arctg— jest zbieżny i bezwzględnie, czy

więcej podobnych podstron