Please enable JavaScript.

Coggle requires JavaScript to display documents.

Mapa Mental 4 - Coggle Diagram

- - - - How fast a alorithm in question runs
    - - The amount of memory a algorithm takes
  - - - C(n)
      - T(n)
  - - - 1º Logarithmic Functions
        (grows slower, hence it's faster)
      - 3º Exponencial Functions
      - 4º Factorial Functions
      - 2º Quadratic Function
  - - - It's when the algorithm is the worst in a n input size, that is, it takes the largest amount of basic operations
    - - When the algorithm runs the faster for a given input with n numbers
    - - The efficiency that the algorithm normally takes, on random inputs.
    - - Sometimes a single operation can be expensive, so this method amortized this expensiveness, such as banks amortize the costs of a debt.
- - - - the set of all functions equal or lower to O(n²)
        
        n ∈ O(n²)
        
        100n + 5 ∈ O(n²)
        
        (1/2)n(n-1) ∈ O(n²)
    - - the set of all functions higher to Ω(n²)
        
        n³ ∈ Ω(n²)
        
        (n(n − 1))/2 ∈ Ω(n²)
        
        100n + 5 ∉ Ω(n²)
    - - if t (n) is bounded both above and below by some positive constant multiples of
        g(n) for all large n.
  - - - Sometimes the algorithm notation leaves out the constant multiplied by it, and it could make worst efficient algorithm goes faster in some cases.
- - - - //Determines the value of the largest element in a given array
      - //Input: An array A[0..n − 1] of real numbers
      - //Output: The value of the largest element in A
    - - Decide on a parameter (or parameters) indicating an input’s size.
      - Identify the algorithm’s basic operation. (As a rule, it is located in the inner-
        most loop.)
      - -
        
        Check whether the number of times the basic operation is executed depends only on the size of an input. If it also depends on some additional property, the worst-case, average-case, and, if necessary, best-case efficiencies have to be investigated separately.
        
        -
      - Set up a sum expressing the number of times the algorithm’s basic operation
        is executed.
      - Using standard formulas and rules of sum manipulation, either find a closed-
        form formula for the count or, at the very least, establish its order of growth.
- - - - Decide on a parameter (or parameters) indicating an input’s size.
        
        Identify the algorithm’s basic operation.
        
        Check whether the number of times the basic operation is executed can vary on different inputs of the same size; if it can, the worst-case, average-case, and best-case efficiencies must be investigated separately.
        
        Solve the recurrence or, at least, ascertain the order of growth of its solution.
        
        Set up a recurrence relation, with an appropriate initial condition, for the
        number of times the basic operation is executed.
- - - - Understand the experiment’s purpose.
      - Decide on the efficiency metric M to be measured and the measurement unit
        (an operation count vs. a time unit).
      - Decide on characteristics of the input sample (its range, size, and so on).
      - Prepare a program implementing the algorithm (or algorithms) for the exper-
        imentation.
      - Generate a sample of inputs.
      - Run the algorithm (or algorithms) on the sample’s inputs and record the data
        observed.
      - Analyze the data obtained.