Please enable JavaScript.

Coggle requires JavaScript to display documents.

EL ANÁLISIS DE ALGORITMOS, División del algoritmo, costo de ordenar un…

- - - - Complejidad computacional
        
        evalúa el tiempo que toma un programa en ejecutarse
        
        Análisis experimental
        
        recursos de hardware, sistema operativo, conjunto de subsistemas
        
        Analisis teorico
        
        Eficiencia de las líneas de código
      - Tiempo ejecución
        
        cálculo del tiempo de ejecución del algoritmo
        
        se halla la función cuadrática del tiempo
        T(n) = an2 + bn + c
      - Tasa crecimiento T(n)
        
        Evalúa el tiempo en función de T
        
        A mayor (n) la ejecución de un algoritmo será más lento
      - Mejor y peor caso
        
        No solo se basa en la función de tiempo si no en eficiencia del algoritmo
        
        evalúa la secuencias que se repiten en el código. se deriva la función de términos comunes
        T(n) = an + b
        
        se halla la función de tiempo cuadratica
        T(n) = an exp 2 + bn + c
      - 5.Notación asintótica
        
        describe la notación del crecimiento de la función de tiempo según su crecimiento
        
        usada para facilitar el examen y comparación de algoritmos en términos de su eficiencia
- - - - combina recursividad
        
        ¿qué es Programación dinámica?
        
        calcular soluciones representadas en ecuaciones de concurrencia
- - - - T(n)= 2T(n/2+0(n) , n>1 o O(1) , n<=1
      - forma general de recurrencia
        
        T(n)= at(d/n)+f(n) ,n>n0 o O(1) , n<n0
- - - - 2<2.81
        
        Aplicar Teorema maestro I
        
        T(n)== T(n) = T(n/2)+O(n) , n>1 o O(1) , n=1
- - - - memoria de los resultados intermedios y así evitar realizar cálculos duplicados.
    - - REQUIERE una estructura iterativa del algoritmo y tiene como consecuencia una reducción considerable de la complejidad de los algoritmos
        
        Tenemos como ejemplo la estructura de fibonasi
        
        F[i] = fib(i).
        
        Fibonacci es un arreglo F con n + 1 posiciones
        
        for i := 2 to n
        
        F[i] := F[i-1] + F[i-2]
        
        return F[n]
        
        fib(n) F[0] := 0 F[1] := 1
        
        su complejidad es 𝚯(n)1.
    - - desprende el siguiente algoritmo recursivo:
        distancia(S[0..m-1], T[0..n-1])
        
        if m = 0 then return n
        if n = 0 then return m
        if S[m-1] = T[n-1] then
        return distancia(S[0..m-2], T[0..n-2])
        return 1 + min( distancia(S[0..m-2], T[0..n-2]), distancia(S[0..m-1], T[0..n-2]),
        distancia(S[0..m-2], T[0..n-1]))
- - - - Certificado y verificador
    - - Reducción de Karp
        
        transformación en tiempo polinómico
        
        A y B problemas
      - NP-Completitud
        
        PROPIEDADES
        i. Está en NP.
        ii. Para todo problema B de la clase NP, existe una reducción de Karp de B en A.
        
        P=NP= NP-C
        
        a
        
        P
        
        b
        
        NP-C
      - Problemas NP-Completo
        
        3-SAT
- - - - fin(2)
        
        fib(1)
        
        fib(0)
      - fin(3)
        
        fin(2)
        
        fib(1)
        
        fib(0)
- - - - T(n) = Ω(√2n) y T(n) = O(2n)
- - - - Ordenamiento de los subarreglos
        
        divide el arreglo en arreglos más pequeños hasta llegar a obtener arreglos con longitud 0 o 1
        
        program ordenar
        
        input: arr: Z[0 .. n-1]
        
        var: a: Z[0 .. ⌊n/2⌋-1], b: Z[0 .. ⌈n/2⌉-1]
        
        íf n ≤ 1 then return
        
        <división del arreglo>
        
        ordenar(a)
        
        ordenar(b)
    - - recibe "a" y "b", como representación a arreglos ordenados
        
        program mezcla
        
        input: a: Z[0 .. m-1], b: Z[0 .. n-1], c: Z[0 .. m+n-1] var: i: Z, j: Z
        
        i⟵0
        
        j⟵0
        
        while i<m or j<n
        
        if i<m and (j=n or a[i]<b[j]) then c[i+j] ⟵ a[i]
        
        i ⟵ i+1 else
        
        c[i+j] ⟵ b[j] j ⟵ j+1