Algorithm#

class Algorithm#

Bases: ComplexityObject, Generic[ProblemInstance, InputSize, ResultInstance]

Base class for all algorithms. Inheriting class should specify type hints for ProblemInstance and InputSize

__init__()#

Methods

`__init__`()
`get_worst_case_arguments`(input_size)	Way to generate keyword arguments for this class' run_algorithm method corresponding to algorithm's worst case scenario.
`increment_n_ops`([increment])	Convenience method to increment n_ops count of the given complexity object.
`reset_n_ops`()	Convenience method to reset n_ops count of the given complexity object.
`run_algorithm`(input_instance[, verbosity_level])	The main run function of each algorithm.

Attributes

`algorithm_family`	rtype: `AlgorithmFamily`
`algorithm_properties`	rtype: `AlgorithmProperties`
`average_case_time_complexity`	rtype: `str`
`best_case_description`	rtype: `str`
`best_case_time_complexity`	rtype: `str`
`is_deterministic`	rtype: `bool`
`n_ops`	rtype: `int`
`name`	rtype: `str`
`space_complexity`	rtype: `str`
`worst_case_description`	rtype: `str`
`worst_case_time_complexity`	rtype: `str`

property algorithm_family: AlgorithmFamily#

Return type:: AlgorithmFamily

abstract property algorithm_properties: AlgorithmProperties#

Return type:: AlgorithmProperties

property average_case_time_complexity: str#

Return type:: str

property best_case_description: str#

Return type:: str

property best_case_time_complexity: str#

Return type:: str

abstract get_worst_case_arguments(input_size)#

Way to generate keyword arguments for this class’ run_algorithm method corresponding to algorithm’s worst case scenario. Output of this function has to be accepted by run_algorithm() and has to contain a pair ‘input_instance’: ProblemInstance with the value having given InputSize.

Parameters:: input_size (InputSize) – Desired input size (form depends on specific algorithm).
Returns:: run_algorithm_kwargs – A dictionary with keyword arguments for the run_algorithm method.
Return type:: dict[str, Any]

increment_n_ops(increment=1)#

Convenience method to increment n_ops count of the given complexity object.

Return type:: None

property is_deterministic: bool#

Return type:: bool

property n_ops: int#

Return type:: int

property name: str#

Return type:: str

reset_n_ops()#

Convenience method to reset n_ops count of the given complexity object.

Return type:: None

abstract run_algorithm(input_instance, verbosity_level=0, *args, **kwargs)#

The main run function of each algorithm. The algorithms should be able to internally count number of ops and should reset self.n_ops to 0 on each use of this method.

Parameters:

input_instance (ProblemInstance) – Instance on which to run the algorithm.
verbosity_level (int (default 0)) – Select the amount of information to print throughout run of the algorithm. One of 0, 1, 2 with 0 typically referring to no printing, 1 leading to print of given ProblemInstance before and after and 2 meaning every step.
*args (Any) – Additional arguments passed to the algorithm.
**kwargs (Any) – Additional keyword arguments passed to the algorithm.

Returns:

result – Returns boolean value representing whether the algorithm terminated successfully and some form of input processed by the algorithm if relevant.

Return type:

tuple[bool, Optional[ResultInstance]]

property space_complexity: str#

Return type:: str

property worst_case_description: str#

Return type:: str

property worst_case_time_complexity: str#

Return type:: str