Demostraci贸n matem谩tica de la correcci贸n y eficiencia del algoritmo

     

    Introducci贸n

    Al dise帽ar un algoritmo completamente nuevo, se necesita un an谩lisis muy completo de su correcci贸n y eficiencia .

    Lo 煤ltimo que querr铆a es que su soluci贸n no sea adecuada para un problema para el que fue dise帽ado en primer lugar.

    En este art铆culo hablaremos de los siguientes temas:

    • Inducci贸n matem谩tica
    • Prueba de correcci贸n
    • Invariantes de bucle
    • An谩lisis de eficiencia: relaciones de recurrencia
    • Relaciones de recurrencia: lineal y no lineal
    • Resoluci贸n de relaciones de recurrencia lineal homog茅nea
    • Teorema de Maestr铆a en Ciencias de la Computaci贸n
    • Ejemplo: programaci贸n din谩mica
    • Ejemplo: b煤squeda binaria
    • Conclusi贸n

    DESCARGO DE RESPONSABILIDAD : como puede ver en los t铆tulos de las secciones, esto no es de ninguna manera, forma o forma destinada a una aplicaci贸n directa. Es Teor铆a de las Ciencias de la Computaci贸n y solo est谩 destinada a una comprensi贸n m谩s profunda de ciertos campos de la programaci贸n pr谩ctica.

    Inducci贸n matem谩tica

    La inducci贸n matem谩tica (MI) es una herramienta esencial para probar la afirmaci贸n que prueba la exactitud de un algoritmo. La idea general de MI es probar que un enunciado es verdadero para cada n煤mero natural n.

    驴Qu茅 significa esto realmente?

    Esto significa que tenemos que seguir 3 pasos:

    • Hip贸tesis de inducci贸n : Defina la regla que queremos probar para cada n, llamemos a la reglaF(n)
    • Base de inducci贸n : demostrar que la regla es v谩lida para un valor inicial, o m谩s bien un punto de partida; esto a menudo se prueba resolviendo la hip贸tesis de inducci贸n F(n)para n=1o cualquier valor inicial que sea apropiado
    • Paso de inducci贸n : demostrar que si sabemos que F(n)es cierto, podemos stepdar un paso adelante y asumir que F(n+1)es correcto

    Si sigui贸 estos pasos, 隆ahora tiene el poder de hacer un bucle! No, de verdad, esto b谩sicamente nos da la posibilidad de hacer algo como esto:

    for (i in range(n)):
        T[i] = True
    

    Ejemplo b谩sico

    Problema :

    Si definimos S(n)como la suma de los primeros nn煤meros naturales, por ejemplo S(3) = 3+2+1, demuestre que la siguiente f贸rmula se puede aplicar a cualquiera n:

    $$
    S (n) = frac {(n + 1) * n} {2}
    $$

    Sigamos nuestros pasos:

    • Hip贸tesis de inducci贸n : S(n)definida con la f贸rmula anterior
    • Base de inducci贸n : En este paso tenemos que demostrar que S(1) = 1:

      $$
      S (1) = frac {(1 + 1) * 1} {2} = frac {2} {2} = 1
      $$

    • Paso de inducci贸n : en este paso debemos demostrar que si la f贸rmula se aplica a S(n), tambi茅n se aplica a S(n+1)lo siguiente:

      $$
      S (n + 1) = frac {(n + 1 + 1) * (n + 1)} {2} = frac {(n + 2) * (n + 1)} {2}
      $$

    Esto se conoce como una implicaci贸n (a => b), lo que simplemente significa que tenemos que demostrar que bes correcto siempre que sepamos que aes correcto.

    $$
    S (n + 1) = S (n) + (n + 1) = frac {(n + 1) * n} {2} + (n + 1) = frac {n ^ 2 + n + 2n + 2} {2}
    $$

    $$
    = frac {n ^ 2 + 3n + 2} {2} = frac {(n + 2) * (n + 1)} {2}
    $$

    Tenga en cuenta que S(n+1) = S(n) + (n+1)solo significa que estamos calculando la suma de forma recursiva. Ejemplo con literales:
    S(3) = S(2) + 3= S(1) + 2 + 3 = 1 + 2 + 3 = 6

    QED

    Prueba de correcci贸n

    Debido a que el m茅todo que estamos usando para probar la correcci贸n de un algoritmo se basa en matem谩ticas, o m谩s bien en funciones , cuanto m谩s similar sea la soluci贸n a una funci贸n matem谩tica real, m谩s f谩cil ser谩 la prueba.

    驴Por qu茅 es esto, puedes preguntar? Bueno, la programaci贸n imperativa pr谩ctica tiene esto llamado estado , esto significa que la salida de un programa depende de 3 cosas:

    • Su secuencia de instrucciones
    • Sus valores de entrada
    • su estado , o m谩s bien, todas las variables previamente inicializadas que pueden cambiar de alguna manera el valor de salida

    Ejemplo de estado de programa

    def foo(x):
        x = y + 1
        return x
    

    Si te pidiera que me dieras el valor de salida de esta funci贸n para x=1, naturalmente dir铆as:

    Bueno, caramba se帽or, 驴c贸mo sabr铆amos el valor de salida si no conocemos ese maldito yvalor?

    Ver谩, ese es exactamente el punto, este programa (imperativo) como cualquier otro tiene un estado , que est谩 definido por una lista de variables y sus valores correspondientes. Solo entonces la salida de este programa es verdaderamente determinista .

    Determinista : un sistema sin factores aleatorios

    Esto abre una historia completamente nueva sobre los paradigmas de programaci贸n que tienen un estado completamente transparente, o en otras palabras, NO TIENEN VARIABLES . Esto puede parecer una locura, pero existe, y se usa con poca frecuencia, especialmente la programaci贸n funcional en Haskell .

    Pero debido a que tradicionalmente no tenemos conceptos funcionales a nuestra disposici贸n en la programaci贸n imperativa, nos conformamos con la siguiente mejor opci贸n para demostrar la correcci贸n: la recursividad . La recursividad es muy f谩cil para la interpretaci贸n matem谩tica porque es equivalente a las relaciones de recurrencia (m谩s sobre las relaciones de recurrencia en los siguientes segmentos).

    Ejemplo de recursividad

    def factorial(n):
        if (n==0):
            return 1
        else:
            return n*factorial(n-1)
    

    Convertido a forma de recurrencia:

    $$
    Factorial (n) = n * Factorial (n-1)
    $$

    Invariantes de bucle

    Todo esto suena bien, pero hasta ahora, no hemos dicho nada sobre la representaci贸n de bucles y estados del programa como f贸rmulas matem谩ticas. Las variables en el estado de un programa plantean un problema porque todas ellas deben mantenerse bajo control todo el tiempo, en caso de que una se vuelva loca.

    Adem谩s, los bucles plantean un problema porque hay muy pocos equivalentes matem谩ticos para ellos. Esto significa que tenemos que incorporar la inducci贸n matem谩tica en nuestro modelo de an谩lisis de algoritmos, porque es el 煤nico m茅todo que conocemos que puede incriminar valores iterativamente en matem谩ticas, como en el c贸digo real.

    La forma m谩s sencilla de resolver ambos problemas (con inducci贸n matem谩tica) son las invariantes de bucle :

    Un ciclo invariante es una f贸rmula l贸gica o simplemente un conjunto de reglas, eso es cierto antes, durante y despu茅s del ciclo en cuesti贸n (por lo que es imparcial a la iteraci贸n). Es imperativo que contenga reglas para todas las variables que ocurren en dicho ciclo porque necesitamos vincularlas todas al conjunto de valores que queremos que sean.

    Selecci贸n de bucle invariante

    Un ciclo invariante puede ser tan complicado y simple como usted quiera. Sin embargo, el punto es que debe construirse para que se asemeje lo m谩s posible al problema en cuesti贸n.

    Por ejemplo, siempre puedo decir que lo siguiente es un ciclo invariante:

    (
    x
    >
    y
    )

    (
    x
    <
    y
    )

    (
    x
    ==
    y
    )

    Pero, al usar una tautolog铆a (una f贸rmula l贸gica que siempre es correcta) como un ciclo invariante, realmente no logramos nada, la 煤nica raz贸n por la que t茅cnicamente se clasifica como un ciclo invariante es que cumple con los 3 requisitos:

    • La f贸rmula es correcta ANTES de la ejecuci贸n del ciclo
    • La f贸rmula es correcta DURANTE la ejecuci贸n del ciclo, incluidos todos los pasos intermedios
    • La f贸rmula es correcta DESPU脡S de la ejecuci贸n del bucle

    Ejemplo:

    Echemos un vistazo al siguiente c贸digo y determinemos el invariante de ciclo 贸ptimo:

    x = 10
    y = 4
    z = 0
    n = 0
    while(n < x):
        z = z+y
        n = n+1
    

    L贸gicamente, este c贸digo simplemente calcula el valor x * y y lo almacena en z, esto significa que z = x*y. Otra condici贸n que sabemos que siempre ser谩 cierta es n <= x(m谩s sobre los iguales en el ejemplo). 驴Pero estos dos realmente solo se aplican despu茅s de que el programa haya terminado de computar?

    El nvalor es esencialmente el n煤mero de bucles que ya se ejecutaron, pero tambi茅n es el n煤mero de veces que el zvalor se ha incrementado y.

    Entonces esto significa que ambos z = n*yy n <= xpueden aplicarse en todo momento . Lo 煤nico que queda por hacer es comprobar si realmente se pueden utilizar como invariantes de bucle.

    Ejemplo de bucle invariante: prueba por inducci贸n

    Primero, necesitamos demostrar que el invariante del ciclo es verdadero antes de entrar en el ciclo (que es el equivalente de la base de prueba y de inducci贸n):

    # <=> - logical equivalency, left and right sides of the equation have the same logical value (True or False)
    # <= - less or equal (not to be confused with implication, which also looks like a arrow to the left)
    x = 10
    y = 4
    z = 0
    n = 0
    # RULE 1: z == n*y
    # 0 == 0*4 = 0 <=> True
    # so RULE 1 applies
    
    # RULE 2: n <= x
    # 0 <= 10 <=> True
    # so RULE 2 applies, therefore the invariant is valid before entering the loop
    

    En segundo lugar, debemos verificar si el invariante es verdadero despu茅s de cada ciclo terminado (excluyendo el 煤ltimo), lo hacemos observando la transici贸n desde z,na z',n', d贸nde z'y n'son los valores de zy ndespu茅s de que se haya ejecutado el siguiente ciclo.

    Por tanto, z' = z+yy n' = n+1. Necesitamos demostrar esencialmente que si sabemos que el invariante es verdadero para zy n, tambi茅n es cierto para z'y n':

    con

    =
    z
    +
    y

    z
    =
    n

    y

    n

    =
    n
    +
    1

    Si lo siguiente es v谩lido, el invariante es v谩lido:聽

    con

    =

    n


    y
    ?

    con

    =
    (
    n
    +
    1
    )

    y
    =
    n

    y
    +
    y
    =
    z
    +
    y

    En tercer lugar, debemos verificar si el invariante es verdadero despu茅s de la 煤ltima iteraci贸n del ciclo. Porque nes un n煤mero entero y sabemos que n-1<xes verdadero, pero n<xfalso, eso significa que n=x(esta es la raz贸n por la que el invariante debe incluir n<=x, no n<x).

    Por eso lo sabemos z = x*y.

    QED

    An谩lisis de eficiencia: relaciones de recurrencia

    Cuando se habla de eficiencia de algoritmos, lo primero que surge son las relaciones de recurrencia. Esto solo significa que una funci贸n como f(n)depende de sus valores anteriores y posteriores, como f(n-1)y f(n+1).

    El ejemplo m谩s simple de este tipo de funci贸n ser铆a la secuencia de Fibonacci:

    $$
    Fibonacci (n) = Fibonacci (n-1) + Fibonacci (n-2)
    $$

    Es posible que reconozca este concepto en mi art铆culo sobre programaci贸n din谩mica. Y s铆, el problema es muy similar, sin embargo, el m茅todo de resoluci贸n es muy diferente.

    Al analizar la eficiencia del algoritmo, hay b谩sicamente dos tipos de relaciones que resolver谩:

    • Relaciones lineales de recurrencia homog茅nea
    • Relaciones de recurrencia no lineales: caso de uso del teorema maestro

    Resoluci贸n de relaciones de recurrencia lineal homog茅nea

    Al leer el t铆tulo anterior, es posible que se pregunte

    “隆驴Qu茅 en el nombre de Dios es este galimat铆as matem谩tico?!?!”

    Bueno, primero echemos un vistazo a la f贸rmula general:

    F
    (
    n
    )
    =

    un
    1

    F
    (
    n

    1
    )
    +

    un
    2

    F
    (
    n

    2
    )
    +
    .
    .
    .
    +

    a
    k

    F
    (
    n

    k
    )
    .

    Ahora dividamos la definici贸n en partes de tama帽o byte (juego de palabras):

    • Lineal se refiere al hecho de que los elementos de la funci贸n F(something)est谩n a la primera potencia
    • Homog茅neo se refiere al hecho de que todos los duplets de elementos a*F(something)son uniformes, lo que significa que una constante no puede estar presente ( a*F(something) = constno puede suceder)

    Estas relaciones de recurrencia se resuelven mediante la siguiente sustituci贸n:

    $$
    (1) F (n) = r ^ n
    $$

    • r ser un n煤mero (complejo) convenientemente elegido

    Enumerar茅 f贸rmulas 煤tiles para poder hacer referencia a ellas m谩s f谩cilmente en el ejemplo

    Estamos usando un n煤mero complejo porque necesitamos una variable que pueda recorrer varios valores, de los cuales todos pueden (pero no es necesario) ser diferentes. Todos los cuales son roots(soluciones) a la ecuaci贸n anterior.

    Aclaraci贸n:

    • complexlos n煤meros tienen una forma de x = a + bi, xsiendo el n煤mero complejo, ay bsiendo enteros simples, y isiendo la constante:
      $$
      begin {align}
      i = sqrt {-1}
      end {align}
      $$
    • como puede notar, ies un n煤mero muy particular, lo que significa que en realidad tiene un ciclo :
      $$
      begin {align}
      i = sqrt {-1},
      i ^ 2 = -1,
      i ^ 3 = -1 * sqrt {-1} ,
      i ^ 4 = 1,
      i ^ 5 = i,
      end {align}
      $$
    • este medio itiene un ciclo delength = 5
    • otros n煤meros complejos se pueden personalizar para tener un ciclo preciso, donde no hay dos elementos iguales (excepto los elementos inicial y final)

    Usando la sustituci贸n mencionada anteriormente, obtenemos el polinomio caracter铆stico :

    r
    k

    un
    1

    r

    k

    1

    un
    2

    r

    k

    2


    .
    .
    .

    a
    k

    =
    0

    Esto representa una ecuaci贸n muy conveniente, donde se rpueden tener kposibles soluciones (ra铆ces). Adem谩s, podemos representar F(n)como una combinaci贸n lineal de todos sus predecesores (la prueba de la correcci贸n de esta f贸rmula no se mostrar谩 por el bien de su cordura y la m铆a):

    F
    (
    n
    )
    =

    i
    =
    1

    a

    c
    yo

    r

    yo

    norte

    • cisiendo coeficientes desconocidos que indican cu谩l rtiene mayor impacto a la hora de calcular el valor deF(n)

    Adem谩s, si el valor de una ra铆z ( rpor ejemplo) aparece m谩s de una vez, decimos que rtiene la multiplicidad ( m) mayor que 1.

    Esto altera ligeramente la ecuaci贸n anterior:

    (
    2
    )

    F
    (
    n
    )
    =

    i
    =
    1

    s

    h
    i

    (
    n
    )

    • hisiendo el elemento que puede contener ri, que se calcula (teniendo en cuenta la multiplicidad) de acuerdo con la f贸rmula:

    (
    3
    )

    h
    i

    (
    n
    )
    =
    (

    C

    yo
    ,
    0

    +

    C

    yo
    ,
    1

    n
    +

    C

    yo
    ,
    2

    n
    2

    +
    .
    .
    .
    +

    C

    i
    ,
    m
    i

    1

    norte

    m
    i


    1

    )

    r
    i
    n

    Felicitaciones, ahora podemos resolver las ecuaciones de recurrencia m谩s b谩sicas. 隆Prob茅moslo!

    Teorema de Maestr铆a en Ciencias de la Computaci贸n

    驴ReStrings cuando dije que lo anterior fueron s贸lo los huesos desnudos recurrencia relaciones? Bueno, ahora veremos un tipo de relaci贸n de recurrencia m谩s complicado, pero mucho m谩s 煤til.

    La forma b谩sica de este nuevo tipo de relaci贸n de recurrencia es:

    $$
    T (n) = aT (frac {n} {b}) + cn ^ k
    $$

    • de los cuales todas las constantes son iguales o mayores que cero a,b,c,k >= 0yb =/= 0

    Esta es una relaci贸n de recurrencia mucho m谩s com煤n porque incorpora el principio de divide y vencer谩s (calcula T(n)calculando un problema mucho m谩s peque帽o como T(n/b)).

    La f贸rmula que usamos para calcular T(n)en el caso de este tipo de relaci贸n de recurrencia es la siguiente:

    T
    (
    n
    )
    =

    {

    O
    (

    norte

    l
    o

    g
    b

    a

    )

    para
    un
    >

    b
    k

    O
    (

    norte

    a

    l
    o
    g

    n
    )

    para
    a
    =

    b
    k

    O
    (

    norte

    a

    )

    para
    un
    <

    b
    k

    Debido a que la f贸rmula anterior es lo suficientemente l贸gica , y debido a que la prueba no es realmente trivial, le aconsejar铆a que la recuerde tal como est谩 … pero si a煤n desea ver la prueba, lea la prueba 1-2 del teorema 5.1 en este art铆culo .

    Ejemplo: b煤squeda binaria

    Si tenemos una matriz ordenada Ade longitud ny queremos saber cu谩nto tiempo nos tomar铆a encontrar un elemento espec铆fico, llam茅moslo zpor ejemplo. Primero debemos echar un vistazo al c贸digo que usaremos para encontrar dicho elemento usando la b煤squeda binaria:

    # leftIndex and rightIndex indicate which part of the original array
    # we are currently examining, the initial function call is find(A,z,1,n)
    import math
    def find(A, z, leftIndex, rightIndex):
        # if our search range is narrowed down to one element,
        # we just check if it's equal to z, target being the index of the wanted element
        # A[target]=z
        if leftIndex == rightIndex:
            if A[leftIndex] == z:
                return leftIndex
            else:
                return -1
        else:
            middlePoint = math.ceil((leftIndex + rightIndex) / 2)
            print("{} {} {}".format(leftIndex, rightIndex, middlePoint))
            # because the array is sorted, we know that if z < X[middlePoint],
            # we know it has to be to the left of said element,
            # same goes if z >= X[middlePoint] and we call
            # find(A, z, leftIndex, middlePoint - 1)
            # if z == A[middlePoint]:
            #     return middlePoint
            if z < A[middlePoint]:
                return find(A, z, leftIndex, middlePoint - 1)
            else:  # z >= A[middlePoint]
                # leaving the middle point in this call is intentional
                # because there is no middle point check
                # except when leftIndex==rightIndex
                return find(A, z, middlePoint, rightIndex)
    
    def main():
        A = [1, 3, 5, 7, 8, 9, 12, 14, 22]
        z = 12
        target = find(A, z, 0, len(A))
        print("Target index: {}".format(target))
    
    if __name__ == "__main__":
        main()
    

    La parte m谩s intensiva en tiempo de esta b煤squeda es la recursividad, esto significa que podemos representar el tiempo que le toma al algoritmo de b煤squeda binaria buscar a trav茅s de una matriz de longitud nusando la siguiente relaci贸n de recurrencia:

    $$
    T (n) = T (frac {n} {2}) + 1
    $$

    La 1representaci贸n de una operaci贸n constante como la verificaci贸n de valor (como leftIndex == rightIndex, esta constante no es realmente tan importante considerando que es mucho m谩s peque帽a que ambos T(n)y T(nb)).

    Al hacer coincidir la f贸rmula b谩sica del teorema maestro con la f贸rmula de b煤squeda binaria, sabemos:

    $$
    a = 1, b = 2, c = 1, k = 0
    $$

    Usando la f贸rmula del teorema maestro para T (n) obtenemos que:

    $$
    T (n) = O (log n)
    $$
    Entonces, la b煤squeda binaria es realmente m谩s eficiente que la b煤squeda lineal est谩ndar.

    Ejemplo: programaci贸n din谩mica VS recursividad

    Echemos un 煤ltimo vistazo a la secuencia de Fibonacci (la 煤ltima vez, lo prometo):

    $$
    Fibonacci (n) = Fibonacci (n-1) + Fibonacci (n-2)
    $$

    La programaci贸n din谩mica, como sabemos por mi 煤ltimo art铆culo, tiene la complejidad de tiempo O(n)porque usa la memorizaci贸n y genera la matriz de forma lineal, sin retrocesos (construye la matriz desde cero).

    Ahora demostremos que es mucho m谩s eficiente usar la programaci贸n din谩mica.

    An谩lisis de complejidad del tiempo de Fibonacci

    Digamos que T(n)representa el tiempo que se necesita para calcular el n-thelemento de la secuencia de Fibonacci.

    Entonces sabemos que se aplica la siguiente f贸rmula:

    $$
    T (n) = T (n-1) + T (n-2)
    $$

    Primero, necesitamos obtener la forma impl铆cita de la ecuaci贸n (las matem谩ticas hablan de colocar todo en un lado, de modo que el otro lado solo tenga un cero):

    $$
    T (n) -T (n-1) -T (n-2) = 0
    $$

    Ahora, usemos la sustituci贸n est谩ndar (f贸rmula (1)):

    $$
    r ^ nr ^ {n-1} -r ^ {n-2} = 0
    $$

    Para simplificar a煤n m谩s la ecuaci贸n, dividamos ambos lados con rla potencia de la potencia m谩s baja presente en la ecuaci贸n (en este caso es n-2):

    r
    n

    r

    n

    1

    r

    n

    2

    =
    0

    /

    r

    n

    2

    r

    n

    (
    n

    2
    )

    r

    n

    1

    (
    n

    2
    )

    r

    n

    2

    (
    n

    2
    )

    =
    0

    r

    2

    r

    1

    r

    0

    =
    0

    r

    2


    r

    1
    =
    0

    Este paso se hace para que podamos resumir el problema en una ecuaci贸n cuadr谩tica .

    Usando la f贸rmula de la ecuaci贸n cuadr谩tica obtenemos los siguientes valores posibles para r:

    r
    1

    =

    1
    +

    5

    2

    ,

    r
    1

    =

    1

    5

    2

    Ahora, usando la f贸rmula (2), determinamos la f贸rmula b谩sica para Fibonacci(n):

    T
    (
    n
    )
    =

    C
    1

    r
    1
    n

    +

    C
    2

    r
    2
    n

    Porque sabemos eso Fibonacci(0) = 0y Fibonacci(1) = 1, por lo tanto, T(0) = 0y T(1) = 1(t茅cnicamente, T(0)y T(1)podr铆a ser cualquier n煤mero constante de operaciones necesarias para calcular sus valores, pero en realidad no afecta tanto el resultado, por lo que en aras de la simplicidad, son 0y 1, solo como Fib(0)y Fib(1)), podemos usarlos para resolver la ecuaci贸n anterior para C1y C2:

    T
    (
    0
    )
    =
    0
    =

    C
    1

    r
    1
    0

    +

    C
    2

    r
    2
    0

    =

    C
    1

    +

    C
    2

    Lo que significa:聽

    C
    1

    =

    C
    2

    Ellos, usando T(1):

    T
    (
    1
    )
    =
    1
    =

    C
    1

    r
    1
    1

    +

    C
    2

    r
    2
    1

    =

    C
    1

    r
    1

    +

    C
    2

    r
    2

    Porque conocemos los valores de `r1` y` r2`, y lo siguiente:聽

    C
    1

    =

    C
    2

    Podemos sustituirlos en la ecuaci贸n principal:聽

    1
    =

    C
    2

    1
    +

    5

    2

    +

    C
    2

    1

    5

    2

    Cuando resolvemos la ecuaci贸n anterior C2obtenemos:

    C
    1

    =

    1

    5

    C
    2

    =

    1

    5

    Lo que significa que ahora tenemos la soluci贸n final a la relaci贸n de recurrencia:

    T
    (
    n
    )
    =

    1

    5


    (

    1
    +

    5

    2

    )
    n

    +

    1

    5


    (

    1

    5

    2

    )
    n

    Deducir la complejidad del algoritmo de la relaci贸n de recurrencia

    Porque T(n)representa el n煤mero de pasos que necesita un programa para calcular el n-thelemento en la secuencia, nsiendo tambi茅n el valor de entrada, o m谩s com煤nmente, el tama帽o de entrada en bits. La soluci贸n anterior nos dice que el algoritmo que estamos usando tiene una complejidad exponencial.

    Hecho de la diversi贸n:

    El m茅todo anterior tambi茅n se puede usar para encontrar la f贸rmula para calcular el valor definido para el n-thelemento en la secuencia de Fibonacci (las funciones representar铆an el valor del n-thelemento en lugar de cu谩ntas operaciones necesita para calcularlas)

    Debido a que O(a^n)(recursiva – complejidad de tiempo exponencial) es un orden de magnitud mucho mayor que O(n)(programaci贸n din谩mica – complejidad de tiempo lineal), ahora tenemos una respuesta definitiva por qu茅 la programaci贸n din谩mica es superior en el tiempo a la recursividad tradicional .

    Conclusi贸n

    S茅 que este art铆culo puede parecer un poco redundante. Pero las pruebas de correcci贸n y eficiencia son las piedras angulares de la teor铆a moderna de la inform谩tica y la principal raz贸n por la que este campo sigue avanzando a un ritmo acelerado.

    La inform谩tica no es lo mismo que la programaci贸n, es solo uno de sus muchos casos de uso. Y creo que ser铆a bueno que la gente entendiera mejor lo que realmente es, al menos 煤nicamente a trav茅s de este art铆culo.

     

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *