Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 132 vistas

    Mcom2 U1 A3 Luac

    Cargado por

    Luis Gerardo Aguilar
    Este documento presenta un algoritmo de ordenamiento y analiza su complejidad, la cual es O(n2) debido a los dos ciclos anidados. También discute la diferencia entre orden de bytes big endian y little endian, y propone un algoritmo de O(n) para invertir el orden de los bytes. Finalmente, demuestra algunas relaciones de complejidad como log(6n)=O(log n) y 3n3=O(n4), pero que 6n2+2 ≠ O(n).

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd

    Mcom2 U1 A3 Luac

    Cargado por

    Luis Gerardo Aguilar
    132 vistas5 páginas
    Este documento presenta un algoritmo de ordenamiento y analiza su complejidad, la cual es O(n2) debido a los dos ciclos anidados. También discute la diferencia entre orden de bytes big endian y little endian, y propone un algoritmo de O(n) para invertir el orden de los bytes. Finalmente, demuestra algunas relaciones de complejidad como log(6n)=O(log n) y 3n3=O(n4), pero que 6n2+2 ≠ O(n).

    Descripción original:

    Actividad 3 de computación 2 unidad 1. UnADM

    Título original

    MCOM2_U1_A3_LUAC

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento presenta un algoritmo de ordenamiento y analiza su complejidad, la cual es O(n2) debido a los dos ciclos anidados. También discute la diferencia entre orden de bytes big endian y little endian, y propone un algoritmo de O(n) para invertir el orden de los bytes. Finalmente, demuestra algunas relaciones de complejidad como log(6n)=O(log n) y 3n3=O(n4), pero que 6n2+2 ≠ O(n).

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    132 vistas5 páginas

    Mcom2 U1 A3 Luac

    Cargado por

    Luis Gerardo Aguilar
    Este documento presenta un algoritmo de ordenamiento y analiza su complejidad, la cual es O(n2) debido a los dos ciclos anidados. También discute la diferencia entre orden de bytes big endian y little endian, y propone un algoritmo de O(n) para invertir el orden de los bytes. Finalmente, demuestra algunas relaciones de complejidad como log(6n)=O(log n) y 3n3=O(n4), pero que 6n2+2 ≠ O(n).

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    Está en la página 1de 5

    Computación 2

    Unidad 1. Introducción a la minería de datos


    Maestra: ELENA TZETZANGARY AGUIRRE MEJIA
    Actividad 3. Análisis de complejidad
    Autor: Luis Gerardo Aguilar Cruz
    Matricula: es1511108497
    domingo, 5 de mayo de 2019
    Actividad 3. Análisis de complejidad | Autor: Luis Gerardo Aguilar Cruz

    Instrucciones: En esta actividad vas a programar y determinar la complejidad de un algoritmo


    previamente escogido.
    1. Considera el siguiente código para hacer ordenamientos
    def algoritmo( entrada )
    n = len( entrada )
    for i in range( n-1 ):
    smallidx = i
    for j in range( i+1, n ):
    if entrada[j] < entrada[smalidx]: smallidx = j
    if smalidx != i:
    tmp = entrada[i]
    entrada[i] = entrada[ smalidx ]
    entrada[smalidx] = tmp

    2. Considera la siguiente situación. Cuando el diseño de las computadoras no estaba


    completamente estandarizado, algunas firmas de electrónica (IBM, Motorola) leían el
    contenido de los bits en memoria de izquierda a derecha (big endian), y otros, como DEC, de
    derecha a izquierda (little endian). Esto claramente causaba discrepancias graves a la hora de
    correr programas hechos para una y otra máquina cuando el problema no es tan grave. De
    hecho, únicamente hay que leer una cadena de bytes en memoria en orden invertido, sin olvidar
    que lo que tienes son cadenas de bytes, es decir, si en una máquina tienes la siguiente cadena,
    en una máquina diseñada con el principio big endian
    00110101 11010110 10110110 00111011

    Debe ser leída en la máquina con little endian de la siguiente manera


    10101100 01101011 01101101 110111100

    3. Contesta las siguientes preguntas


    a) ¿Cuál es la complejidad asociada al algoritmo recién presentado?
    Debido a que cuenta con dos ciclos for anidados su complejidad es 𝑂(𝑛2 )

    1
    b) Diseña un algoritmo que invierta los bytes en un tiempo Ο(𝑛2 ); (recuerda que la definición
    de Ο(𝑓(𝑛)) representa una cota superior del orden de 𝑓(𝑛), es decir, el tiempo máximo
    que debería tomar al algoritmo ejecutarse).

    Bueno, diseñe un algoritmo que invierte los bytes en un tiempo 𝑂(𝑛)

    c) Demuestra que, y que log(6𝑛) = Ο(log 𝑛), 3𝑛3 = Ο(𝑛4 ) y que 6𝑛2 + 2 ≠ Ο(𝑛)
    log(6𝑛) = Ο(log 𝑛)
    Dadas dos funciones f(n) y g(n) diremos que f(n) es equivalente a g(n) cuando
    𝑓(𝑛)
    lim ( )=𝐾
    𝑛→∞ 𝑔(𝑛)

    Sea 𝑓(𝑛) = log(6𝑛) , 𝑔(𝑛) = 𝑂(log 𝑛)


    log(6𝑛) log 𝑛 + log 6
    lim ( ) = lim ( )
    𝑛→∞ log 𝑛 n→∞ log 𝑛
    𝑑
    (log 𝑛 + log 6)
    = lim (𝑑𝑛 )
    n→∞ 𝑑
    (log 𝑛)
    𝑑𝑛
    Actividad 3. Análisis de complejidad | Autor: Luis Gerardo Aguilar Cruz

    1/𝑛
    = lim ( ) = lim 1 = 1
    𝑛→∞ 1/𝑛 𝑛→∞

    Por lo tanto, log(6𝑛) = Ο(log 𝑛)


    Es decir, log(6𝑛) ∈ Ο(log 𝑛)
    ∎
    3𝑛3 = Ο(𝑛4 )
    Dadas dos funciones f(n) y g(n) diremos que f(n) es menos compleja que g(n) cuando
    𝑓(𝑛)
    lim ( )=0
    𝑛→∞ 𝑔(𝑛)

    Sea 𝑓(𝑛) = 3𝑛3 , 𝑔(𝑛) = Ο(𝑛4 )


    3𝑛3 3
    lim ( 4 ) = lim ( ) = 0
    𝑛→∞ 𝑛 𝑛→∞ 𝑛

    Por lo tanto, 3𝑛3 = 𝑂(𝑛4 )


    Es decir, 3𝑛3 ∈ 𝑂(𝑛4 ).
    ∎
    6𝑛2 + 2 ≠ Ο(𝑛)
    Dadas dos funciones f(n) y g(n) diremos que f(n) es más compleja que g(n) cuando
    𝑓(𝑛)
    lim ( )=∞
    𝑛→∞ 𝑔(𝑛)

    Sea 𝑓(𝑛) = 6𝑛2 + 2, 𝑔(𝑛) = Ο(𝑛)


    6𝑛2 + 2 𝑛(6𝑛 + 2/𝑛)
    lim ( ) = lim ( ) = lim (6𝑛 + 2/𝑛) = ∞ + 0 = ∞
    𝑛→∞ 𝑛 𝑛→∞ 𝑛 𝑛→∞

    Por lo tanto, 6𝑛2 + 2 ≠ Ο(𝑛)


    Es decir, 6𝑛2 + 2 ∉ Ο(𝑛)
    ∎

    3
    Referencias
    Mañas, J. A. (10 de febrero de 2017). Análisis de algoritmos - Complejidad. Obtenido de
    Universidad Politécnica de Madrid:
    http://web.dit.upm.es/~pepe/doc/adsw/tema1/Complejidad.pdf
    pildorasinformaticas. (24 de enero de 2017). Curso Python desde 0 (lista de reproducción).
    Obtenido de YouTube:
    https://www.youtube.com/playlist?list=PLU8oAlHdN5BlvPxziopYZRd55pdqFwkeS
    Rossum, G. v. (octubre de 2017). El tutorial de Python. Obtenido de
    http://docs.python.org.ar/tutorial/pdfs/TutorialPython3.pdf
    UnADM. (s.f.). Computación 2. Unidad 1. Introducción a la minería de datos. Obtenido de Aula
    virtual: https://unadmexico.blackboard.com

    También podría gustarte