orbital.algorithm.template
Class DivideAndConquer

java.lang.Object
  orbital.algorithm.template.DivideAndConquer

All Implemented Interfaces:

AlgorithmicTemplate

public class DivideAndConquer
extends java.lang.Object
implements AlgorithmicTemplate

Framework (template class) for Divide and Conquer Algorithms.

top-down technique

Author:

Uwe Aßmann, André Platzer

See Also:

DivideAndConquerProblem

Attributes:

stateless

Nested Class Summary

Nested classes/interfaces inherited from interface orbital.algorithm.template.AlgorithmicTemplate

AlgorithmicTemplate.Configuration

Constructor Summary

DivideAndConquer()

Method Summary

Function	complexity() ≈O(n*㏒ n).
java.lang.Object	solve(AlgorithmicProblem p) Generic solve method for a given algorithmic problem.
java.lang.Object	solve(DivideAndConquerProblem p) solves by divide and conquer.
Function	spaceComplexity() Measure for the asymptotic space complexity of the central solution operation in O-notation.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DivideAndConquer

public DivideAndConquer()

Method Detail

solve

public java.lang.Object solve(AlgorithmicProblem p)

Description copied from interface: AlgorithmicTemplate

Generic solve method for a given algorithmic problem.

Specified by:

solve in interface AlgorithmicTemplate

Parameters:

p - algorithmic problem hook class which must fit the concrete algorithmic template framework implementation.

Returns:

the solution to the problem p, or null if solving failed.

See Also:

Function.apply(Object)

solve

public java.lang.Object solve(DivideAndConquerProblem p)

solves by divide and conquer.

Returns:

the solution object as merged from the partial problems.

Postconditions:

solution is a merge of partial solutions.

complexity

public Function complexity()

≈O(n*㏒ n). With O(㏒ n) for divide and conquer and O(n) for each merge.

More precisely, if you have a recurrence T(n) that describes the running time of a divide and conquer algorithm that divides a problem of size n into p subproblems of size n/d, each, and the cost of dividing and merging a problem of size n is f(n), you can apply the master theorem to find an precise asymptotic bound for the running time T(n).

Master Theorem

Let T(n) = p*T([n/d]) + f(n) with p≥1,d>1,f:N→R. Then

T(n) ∈	{	Θ(n㏒dp)	⇐ ∃ε>0 f(n)∈O(n㏒dp-ε)
		Θ(n㏒dp⋅㏒n)	⇐ f(n)∈Θ(n㏒dp)
		Θ(f(n))	⇐ ∃ε>0 f(n)∈Ω(n㏒dp+ε) ∧ ∃c<1 p⋅f([n/d]) ≤ c⋅f(n) p.t. n∈N

Note that we can either choose [n/d] to be the gaussian floor ⌊n/d⌋, or the gaussian ceiling ⌈n/d⌉, with both choices achieving the same asymptotic behaviour.

Specified by:

complexity in interface AlgorithmicTemplate

Returns:

the function f for which the solve() method of this algorithm runs in O(f(n)) assuming the algorithmic problem hook to run in O(1).

See Also:

AlgorithmicTemplate.solve(AlgorithmicProblem)

spaceComplexity

public Function spaceComplexity()

Description copied from interface: AlgorithmicTemplate

Measure for the asymptotic space complexity of the central solution operation in O-notation.

Specified by:

spaceComplexity in interface AlgorithmicTemplate

Returns:

the function f for which the solve() method of this algorithm consumes memory with an amount in O(f(n)) assuming the algorithmic problem hook uses space in O(1).

See Also:

AlgorithmicTemplate.solve(AlgorithmicProblem)