Please enable JavaScript.

Coggle requires JavaScript to display documents.

DIVIDE ET IMPERA - Coggle Diagram

- - - - b > 1
      - f(n) Asintoticamente positiva
        
        se af(n/b) <= cf(n)
        
        T(n) = Θ(f(n))
      - a >= 1
  - - - IPOTIZZA SOLUZIONE
      - DIMOSTRAZIONE PER INDUZIONE
        
        ATTENZIONE CASO BASE
- - - - RIERCA VALORE IN UN ARRAY
    - - ARRAY
      - VALORE DA CERCARE
    - - POSIZIONE DEL VALORE NELL'ARRAY
  - - - DIVIDE
        
        i = INDICE MEDIANO
        
        2 SOTTOARRAY
      - IMPERA
        
        SE K < A[i]
        
        RICERCA BINARIA RICORSIVA IN A[1, ... , I-1]
        
        SE K > A[i]
        
        RICERCA BINARIA RICORSIVA IN A[I+1, ... , N]
      - COMPLESSITA'
        
        CASO BASE
        
        Θ(1) , per n=0,1
        
        CASO RICORSIVO
        
        𝑇(𝑛/2) + Θ(1), per n>1
- - - - CONTROLLO INDICE PER INDICE
    - - IMPERA
        
        CERCA MASSIMO IN
        
        A[low, ... , mid]
        
        A[mid+1, ... , high]
      - COMBINA
        
        CERCA MASSIMO A CAVALLO
      - DIVIDE
        
        TROVA MID