Please enable JavaScript.

Coggle requires JavaScript to display documents.

Verificación formal de programas 2 - Coggle Diagram

- - - - Según el enunciado del teorema , si tenemos una ecuación de recurrencia de la forma T(n) = aT(n/b) + f(n), donde a ≥ 1, b > 1 y f(n) es una función asintóticamente positiva, entonces:
      - i. Si f(n) = O(n^c) para algún c < log_b(a), entonces T(n) = Θ(n^log_b(a)).
      - ii. Si f(n) = Θ(n^log_b(a) log^k(n)), donde k ≥ 0, entonces T(n) = Θ(n^log_b(a) log^(k+1)(n)).
      - iii. Si f(n) = Ω(n^c) para algún c > log_b(a), y si a f(n/b) ≤ k f(n) para alguna constante k < 1 y suficientemente grande n, entonces T(n) = Θ(f(n)).
      - En el ejemplo del algoritmo de ordenamiento por mezcla , se aplica el caso ii del teorema maestro, lo que nos permite concluir que T(n) = Θ(n log n).
- - - - El algoritmo de mezcla combina las dos mitades ordenadas de manera eficiente para obtener un arreglo finalmente ordenado. En el texto , se menciona que el algoritmo de mezcla tiene un orden de complejidad de O(n log n), lo que significa que su tiempo de ejecución crece de manera logarítmica con respecto al tamaño del arreglo.