Teknisk databehandling Tom Smedsaas

September 21, 2000

Huvudsats för analys av divide and conquer-algoritmer

Detta papper presenterar en variant av den huvudsats för lösning av de differensekvationer som ofta erhålles vid analys av divide and conquer- algoritmer som boken beskriver i kapitel 4.3 och 4.4. Satsen är mindre generell än den som finns i boken men är lite lättare att förstå och bevisa och den illustrerar hur samspelet mellan antalet delproblem och deras storlek påverkar exekveringstiden.

Divide and conquer-algoritmer

Antag att vi har ett problem av storlek n och att vi löser det genom att dela upp det i a stycken delproblem vardera av storlek n/b. Antag också att arbetet att skapa delproblemen samt att kombinera lösningarna av dessa till en lösning av ursprungsproblemet är f(n). Då kan tiden T (n) för att lösa problemet skrivas med följande differensekvation:

T (n) = aT (\frac{n}{b}) + f (n)  (1)

där a > 0 och b > 1 är heltal.

Exempel 1 Binär sökning i en sorterad array. Där är a = 1, b = 2 och f(n) = c

Exempel 2 Samsortering (mergesort). Där är a = 2, b = 2 och f(n) = cn

Vanligt förekommande funktioner f(n) är polynom som i exemplen ovan. Vi väljer därför att formulera och bevisa satsen för f(n) = cn.

Påstående Om

\begin{aligned}T (1) & = c \\ T (n) & = aT (\frac{n}{b}) + cn \end{aligned}  (2)

där a > 0, b > 1 och c ≥ 0 är heltal så gäller att T (n) är

O(n) om a < b  (3)
Θ(n log n) om a = b  (4)
Θ(n^{log_{b} a}) om a > b  (5)

Bevis Vi begränsar oss till fallet att n är en jämn b-potens dvs att n = b^{k}, k = log_{b} n.

Genom att använda formel (2) upprepade gånger och utnyttja att argumentet alltid går att dela med b så erhålles:

\begin{aligned}T (n) & = aT (\frac{n}{b}) + cn = a [aT (\frac{n}{b^{2}} ) + c\frac{n}{b}] + cn \\ & = a^{2}T (\frac{n}{b^{2}} ) + cn\frac{a}{b} + cn \\ & = a^{3}T (\frac{n}{b^{3}} ) + cn (\frac{a}{b})^{2} + cn\frac{a}{b} + cn \\ & = ⋯ \\ & = a^{k}T (\frac{n}{b^{k}} ) + cn ∑_{i=0}^{k−1} (\frac{a}{b})^{i} \\ & = a^{k}T (1) + cn ∑_{i=0}^{k−1} (\frac{a}{b})^{i} \\ & = a^{k}c + cn ∑_{i=0}^{k−1} (\frac{a}{b})^{i} \end{aligned}  (6)

Med hjälp av sambandet x^{log y} = y^{log x} blir den första termen

a^{k}c = a^{log_{b} n}c = cn^{log_{b} a}  (7)

För att beräkna summationen i den andra termen är det bra att skilja på tre fall: Fall 1: a < b

∑_{i=0}^{k−1} (\frac{a}{b})^{i} < ∑_{i=0}^{∞} (\frac{a}{b})^{i} = \frac{1}{1 − a/b}  (8)

vilket ger

T (n) < cn^{log_{b} a} + \frac{c}{1 − a/b}n < cn + \frac{c}{1 − a/b}n  (9)

som är O(n) Fall 2: a = b

∑_{i=0}^{k−1} (\frac{a}{b})^{i} = ∑_{i=0}^{k−1} 1^{i} = k = log_{b} n  (10)

vilket ger

T (n) = cn^{log_{b} b} + cn log_{b} n = cn + cn log_{b} n  (11)

som är Θ (n log n) Fall 3: a > b

∑_{i=0}^{k−1} (\frac{a}{b})^{i} = \frac{(a/b)^{k} − 1}{a/b − 1}  (12)
(a/b)^{k} = (a/b)^{log_{b} n} = n^{log^{b}(a/b)} = n^{log_{b} a−log_{b} b} = n^{log_{b} a−1}  (13)

Således

T (n) = cn^{log_{b} a} + cn\frac{(a/b)^{k} − 1}{a/b − 1} = cn^{log_{b} a} + cn\frac{n^{log_{b} a−1} − 1}{a/b − 1}

= cn^{log_{b} a} + \frac{cn^{log_{b} a} − cn}{a/b − 1}

(14)

som är Θ(n^{log_{b} a}) eftersom log_{b} a > 1

Därmed är alla tre fallen bevisade.

Övning 1 Bevisa att om

\begin{aligned}T (1) & = c \\ T (n) & = aT (\frac{n}{b}) + c \end{aligned}  (15)

där a > 0, b > 1 och c ≥ 0 är heltal så gäller att T (n) är

Θ(log n) om a = 1  (16)
Θ(n^{log_{b} a}) om a > 1  (17)

Övning 2 Produkten av två stycken 2 × 2-matriser kan definieras som

( \begin{matrix}A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix} ) × ( \begin{matrix}A_{11} & B_{12} \\ B_{21} & B_{22} \end{matrix} ) =

( \begin{matrix}A_{11}B_{11} + A_{12}B_{21} & A_{11}B_{12} + A_{12}B_{22} \\ A_{21}B_{11} + A_{22}B_{21} & A_{21}B_{12} + A_{22}B_{22} \end{matrix} ) (18)

Denna formel kan användas för att, på divide and conquer-sätt definiera multiplikation av godtyckliga matriser. Om vi för enkelhets skull antar att n är “tillräckligt” delbart med 2 så kan multiplikation av n × n-matrisern A och B definieras enligt ovan där A_{ij} och B_{ij} är kvadratiska delmatriser av dimension (n/2)×(n/2). En multiplikation av två stycken n×n-matriser kan alltså utföras med hjälp av åtta multiplikationer och fyra additioner av (n/2)×(n/2)-matriser.

Hur många skalära aritmetiska operationer (additioner och multiplikationer) av tal använder ovanstående algoritm?

Övning 3 Enligt V. Strassen kan matrisprodukten ovan också definieras genom att man beräknar sju nya (n/2) × (n/2)-matriser:

\begin{aligned}M_{1} & = (A_{12} − A_{22})(B_{21} + B_{22}) \\ M_{2} & = (A_{11} + A_{22})(B_{11} + B_{22}) \\ M_{3} & = (A_{11} − A_{21})(B_{11} + B_{12}) \\ M_{4} & = (A_{11} + A_{12})B_{22} \\ M_{5} & = A_{11}(B_{12} − B_{22}) \\ M_{6} & = A_{22}(B_{21} − B_{11}) \\ M_{7} & = (A_{21} + A_{22})B_{11} \end{aligned}  (19)

varefter de fyra delarna av produktmatrisen erhålles genom

\begin{aligned}C_{11} & = M_{1} + M_{2} − M_{4} + M_{6} \\ C_{12} & = M_{4} + M_{5} \\ C_{21} & = M_{6} + M_{7} \\ C_{22} & = M_{2} − M_{3} + M_{5} − M_{7} \end{aligned}  (20)

(Kan ganska enkelt verifieras för 2 × 2-matriser) Är denna metod snabbare eller långsammare än metoden i övning 2?