Please enable JavaScript.

Coggle requires JavaScript to display documents.

Algorithm Part I, Union-Find, Analysis of Algorithms - Coggle Diagram

- - - - i 0 1 2 3 4 5 6 7 8 9
        id[i] 0 9 6 5 4 2 6 1 0 5
        
        root of 3 and 7
        
        The root of 3 is 6: 3→5→2→6.
        The root of 7 is 6: 7→1→9→5→2→6.
    - - number of array access
    - - too expensive to keep trees flat
  - - - find takes proportional time
      - union takes constant time, given roots.
      - Proposition: Depth of any node x is at mos lg N.
      - analyze running time mathematically
- - - - takes n log n
    - - takes n log n
  - - - O(1)
        
        Constant operation, not cost time
        
        Fix cost
      - O(n) depends of n (large more time)
        
        loop
      - O(n^2), for two loops (quadratic)
        
        share to conquer