Enum 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 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
      • 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
      • LINEAR

        public static final Complexity LINEAR
        Linear. Example: Finding the smallest or largest item in an unsorted array.

        O(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
      • 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 Detail

      • formula

        private final java.lang.String formula
    • Constructor Detail

      • Complexity

        private Complexity​(java.lang.String formula)
    • 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 name
        java.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 class java.lang.Enum<Complexity>