Please enable JavaScript.

Coggle requires JavaScript to display documents.

M1 (Fundamentals of the analysis of algorithm efficiency, Brute-force,…

- - - - Basic operation
      - Number of times the basic operation is executed on inputs of size n
        C(n)
    - - log_2(n) > n > n.log_2(n) > n^2 > n^3 > 2^n > n!
      - 2^n and n! = exponential-growth functions
      - Algortihms that require an exponential number of operations are practical for solving only problems of very small sizes
    - - Worst-case
        
        Efficiency for the worst-case input of size n
        
        Guarantees that for any instance of size n, the running time wil not exceed C_{worst}(n)
      - Best-case
        
        Efficiency for the best-case input of size n
        
        Not as important as the worst-case
        
        If the best-case is unsatisfactory, the algorithm can be discarted without further analysis
      - Avarege-case
        
        Algorithm's behaviour on typical or random inputs
        
        C_{avg}(n)
        
        The investigation is more difficult than the worst and best cases
      - Amortized efficiency
  - - - t(n) <= c.g(n)
      - O(g(n)) is the set of all functions with a lower or same order of growth as g(n)
      - "Maximum"
    - - t(n) >= c.g(n)
      - big-omega(g(n) is the set of all functions with a higher or same order of growth as g(n)
      - "Minimal"
    - - c_2.g(n) <= t(n) <= c_2.g(n)
      - big-theta(g(n)) is the set of all functions that hace the same order of growth as g(n)
    - - if t_1(n) belongs to O(g_1(n)) and t_2(n) belongs to O(g_2(n)), then t_1 + t_2 belongs to O(max{g_1(n), g_2(n)})
      - Also true for big-omega and big-theta
    - - n tending to infinity
      - if the division is equal to 0 or a constant, it means that t(n) belong to the big-oh of g(n)
      - if the division tends to a constant or infinity, it means that t(n) belongs to the big-omega of g(n)
      - if the division tends to infinity, it means that t(n) belongs to the big-theta of g(n)
      - t(n) / g(n)
      - using limits allows us to user powerful calculus technique like L'Hôpital's rule
  - - - Decide on a parameter indicating an input's site
        
        Identify the basic operation (Innermost loop)
        
        Is it necessary to investigate the worst, average or best-case efficiencies
        
        Set up a sum expressing the number of times the basic operation is executed
        
        Manipulate the sum and either find a closed-form formula for the count or establish its order of growth
  - - - Backward substitituion
      - Smoothness rule
    - - Decide on a parameter indicating an input's size
        
        Identify the basic operation
        
        Check if it's necessary to investigate the worst, best and average-cases
        
        Set a recurrence relation with an appropriate initial condition
        
        Solve the recurrence or ascertain the order of growth of its solution
  - - - Understand the experiment's purpose
        
        Decide on the efficiency metric to be measured and the measurement unit
        
        Decide on characteristics of the input sample (range, size, etc)
        
        Implement the algorithm on a program
        
        Generate a sample of inputs
        
        Run the algorithm on the sample and record the data
        
        Analyze the data obtained
  - - - Static algorithm visualization
        Shows progress as a series of still images
      - Dynamic algorithm visualization (Algorithm animation):
        Continuous, movie-like presentation of operations
        More sophisticated and difficult
        Sorting Out Sorting