Enum Complexity

java.lang.Object
java.lang.Enum<Complexity>
com.igormaznitsa.meta.Complexity
All Implemented Interfaces:
Serializable, Comparable<Complexity>

public enum Complexity extends Enum<Complexity>
Complexity constants. List was taken from the wiki page.
Since:
1.1.2
  • Enum Constant Details

    • 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
      Logarithmic. Example: Binary search.

      O(log n)

      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 invalid input: '<' c invalid input: '<' 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
  • Field Details

    • formula

      private final String formula
  • Constructor Details

    • Complexity

      private Complexity(String formula)
  • Method Details

    • values

      public static Complexity[] 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

      public static Complexity valueOf(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:
      IllegalArgumentException - if this enum type has no constant with the specified name
      NullPointerException - if the argument is null
    • getFormula

      public String getFormula()
      Get the formula.
      Returns:
      formula as string
      Since:
      1.1.2
    • toString

      public String toString()
      Overrides:
      toString in class Enum<Complexity>