Package com.igormaznitsa.meta
Enum Complexity
- All Implemented Interfaces:
Serializable
,Comparable<Complexity>
Complexity constants. List was taken from the wiki page.
- Since:
- 1.1.2
-
Enum Constant Summary
Enum ConstantsEnum ConstantDescriptionConstant value. Example: Determining if an integer (represented in binary) is even or odd.Cubic.Factorial.Fractional power.Inverse Ackermann. Example: Amortized time per operation using a disjoint set.Log-logarithmic. Example: Amortized time per operation using a bounded priority queue.Logarithmic. Example: Binary search.n log star n.Quadratic. -
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionGet the formula.toString()
static Complexity
Returns the enum constant of this type with the specified name.static Complexity[]
values()
Returns an array containing the constants of this enum type, in the order they are declared.
-
Enum Constant Details
-
CONSTANT
Constant value. Example: Determining if an integer (represented in binary) is even or odd.O(1)
- Since:
- 1.1.2
-
INVERSE_ACKERMANN
Inverse Ackermann. Example: Amortized time per operation using a disjoint set.O(α(n))
- Since:
- 1.1.2
-
ITERATED_LOGARITHMIC
- Since:
- 1.1.2
-
LOG_LOGARITHMIC
Log-logarithmic. Example: Amortized time per operation using a bounded priority queue.O(log log n)
- Since:
- 1.1.2
-
LOGARITHMIC
- Since:
- 1.1.2
-
POLYLOGARITHMIC
Polylogarithmic.poly(log n)
- Since:
- 1.1.2
-
FRACTIONAL_POWER
Fractional power. Example: Searching in a kd-tree.O(nc) where 0 invalid input: '<' c invalid input: '<' 1
- Since:
- 1.1.2
-
LINEAR
Linear. Example: Finding the smallest or largest item in an unsorted array.O(n)
- Since:
- 1.1.2
-
N_LOG_STAR_N
n log star n. Example: Seidel's polygon triangulation algorithm.O(n log* n)
- Since:
- 1.1.2
-
LINEARITHMIC
Lineqarithmic. Example: Fastest possible comparison sort.O(n log n)
- Since:
- 1.1.2
-
QUADRATIC
Quadratic. Example: Bubble sort; Insertion sort; Direct convolution.O(n2)
- Since:
- 1.1.2
-
CUBIC
Cubic. Example: Naive multiplication of two n×n matrices. Calculating partial correlation.O(n3)
- Since:
- 1.1.2
-
POLYNOMIAL
Polynomial. Example: Karmarkar's algorithm for linear programming; AKS primality test.2O(log n) = poly(n)
- Since:
- 1.1.2
-
QUASI_POLYNOMIAL
Quasi-polinomial. Example: Best-known O(log2 n)-approximation algorithm for the directed Steiner tree problem.2poly(log n)
- Since:
- 1.1.2
-
SUB_EXPONENTIAL
Sub-exponential. Example: Assuming complexity theoretic conjectures, BPP is contained in SUBEXP.O(2nε) for all ε > 0
- Since:
- 1.1.2
-
EXPONENTIAL
Exponential. Example: Solving matrix chain multiplication via brute-force search.2O(n)
- Since:
- 1.1.2
-
FACTORIAL
Factorial. Example: Solving the traveling salesman problem via brute-force search.O(n!)
- Since:
- 1.1.2
-
DOUBLE_EXPONENTIAL
Double exponential. Example: Deciding the truth of a given statement in Presburger arithmetic.22poly(n)
- Since:
- 1.1.2
-
-
Field Details
-
formula
-
-
Constructor Details
-
Complexity
-
-
Method Details
-
values
Returns an array containing the constants of this enum type, in the order they are declared.- Returns:
- an array containing the constants of this enum type, in the order they are declared
-
valueOf
Returns the enum constant of this type with the specified name. The string must match exactly an identifier used to declare an enum constant in this type. (Extraneous whitespace characters are not permitted.)- Parameters:
name
- the name of the enum constant to be returned.- Returns:
- the enum constant with the specified name
- Throws:
IllegalArgumentException
- if this enum type has no constant with the specified nameNullPointerException
- if the argument is null
-
getFormula
Get the formula.- Returns:
- formula as string
- Since:
- 1.1.2
-
toString
- Overrides:
toString
in classEnum<Complexity>
-