Package com.igormaznitsa.meta
Enum Complexity
- java.lang.Object
-
- java.lang.Enum<Complexity>
-
- com.igormaznitsa.meta.Complexity
-
- All Implemented Interfaces:
java.io.Serializable
,java.lang.Comparable<Complexity>
public enum Complexity extends java.lang.Enum<Complexity>
Complexity constants. List was taken from the wiki page.- Since:
- 1.1.2
-
-
Enum Constant Summary
Enum Constants Enum Constant Description CONSTANT
Constant value. Example: Determining if an integer (represented in binary) is even or odd.CUBIC
Cubic.DOUBLE_EXPONENTIAL
EXPONENTIAL
FACTORIAL
Factorial.FRACTIONAL_POWER
Fractional power.INVERSE_ACKERMANN
Inverse Ackermann. Example: Amortized time per operation using a disjoint set.ITERATED_LOGARITHMIC
LINEAR
LINEARITHMIC
LOG_LOGARITHMIC
Log-logarithmic. Example: Amortized time per operation using a bounded priority queue.LOGARITHMIC
Logarithmic. Example: Binary search.N_LOG_STAR_N
n log star n.POLYLOGARITHMIC
POLYNOMIAL
QUADRATIC
Quadratic.QUASI_POLYNOMIAL
SUB_EXPONENTIAL
-
Field Summary
Fields Modifier and Type Field Description private java.lang.String
formula
-
Constructor Summary
Constructors Modifier Constructor Description private
Complexity(java.lang.String formula)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description java.lang.String
getFormula()
Get the formula.java.lang.String
toString()
static Complexity
valueOf(java.lang.String name)
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 Detail
-
CONSTANT
public static final Complexity CONSTANT
Constant value. Example: Determining if an integer (represented in binary) is even or odd.O(1)
- Since:
- 1.1.2
-
INVERSE_ACKERMANN
public static final Complexity INVERSE_ACKERMANN
Inverse Ackermann. Example: Amortized time per operation using a disjoint set.O(α(n))
- Since:
- 1.1.2
-
ITERATED_LOGARITHMIC
public static final Complexity ITERATED_LOGARITHMIC
- Since:
- 1.1.2
-
LOG_LOGARITHMIC
public static final Complexity LOG_LOGARITHMIC
Log-logarithmic. Example: Amortized time per operation using a bounded priority queue.O(log log n)
- Since:
- 1.1.2
-
LOGARITHMIC
public static final Complexity LOGARITHMIC
- Since:
- 1.1.2
-
POLYLOGARITHMIC
public static final Complexity POLYLOGARITHMIC
Polylogarithmic.poly(log n)
- Since:
- 1.1.2
-
FRACTIONAL_POWER
public static final Complexity FRACTIONAL_POWER
Fractional power. Example: Searching in a kd-tree.O(nc) where 0 < c < 1
- Since:
- 1.1.2
-
LINEAR
public static final Complexity LINEAR
Linear. Example: Finding the smallest or largest item in an unsorted array.O(n)
- Since:
- 1.1.2
-
N_LOG_STAR_N
public static final Complexity N_LOG_STAR_N
n log star n. Example: Seidel's polygon triangulation algorithm.O(n log* n)
- Since:
- 1.1.2
-
LINEARITHMIC
public static final Complexity LINEARITHMIC
Lineqarithmic. Example: Fastest possible comparison sort.O(n log n)
- Since:
- 1.1.2
-
QUADRATIC
public static final Complexity QUADRATIC
Quadratic. Example: Bubble sort; Insertion sort; Direct convolution.O(n2)
- Since:
- 1.1.2
-
CUBIC
public static final Complexity CUBIC
Cubic. Example: Naive multiplication of two n×n matrices. Calculating partial correlation.O(n3)
- Since:
- 1.1.2
-
POLYNOMIAL
public static final Complexity POLYNOMIAL
Polynomial. Example: Karmarkar's algorithm for linear programming; AKS primality test.2O(log n) = poly(n)
- Since:
- 1.1.2
-
QUASI_POLYNOMIAL
public static final Complexity 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
public static final Complexity SUB_EXPONENTIAL
Sub-exponential. Example: Assuming complexity theoretic conjectures, BPP is contained in SUBEXP.O(2nε) for all ε > 0
- Since:
- 1.1.2
-
EXPONENTIAL
public static final Complexity EXPONENTIAL
Exponential. Example: Solving matrix chain multiplication via brute-force search.2O(n)
- Since:
- 1.1.2
-
FACTORIAL
public static final Complexity FACTORIAL
Factorial. Example: Solving the traveling salesman problem via brute-force search.O(n!)
- Since:
- 1.1.2
-
DOUBLE_EXPONENTIAL
public static final Complexity DOUBLE_EXPONENTIAL
Double exponential. Example: Deciding the truth of a given statement in Presburger arithmetic.22poly(n)
- Since:
- 1.1.2
-
-
Method Detail
-
values
public static Complexity[] values()
Returns an array containing the constants of this enum type, in the order they are declared. This method may be used to iterate over the constants as follows:for (Complexity c : Complexity.values()) System.out.println(c);
- Returns:
- an array containing the constants of this enum type, in the order they are declared
-
valueOf
public static Complexity valueOf(java.lang.String name)
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:
java.lang.IllegalArgumentException
- if this enum type has no constant with the specified namejava.lang.NullPointerException
- if the argument is null
-
getFormula
public java.lang.String getFormula()
Get the formula.- Returns:
- formula as string
- Since:
- 1.1.2
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Enum<Complexity>
-
-