Notación Big O - Python

1. Definición

Notación matemática que describe el límite superior del tiempo de ejecución o el uso de espacio de un algoritmo. Se denota como O(f(n)), donde f(n) es una función que representa el tiempo o espacio en función del tamaño de la entrada n.

Mas información visita: http://bigocheatsheet.com

2. Propósito

Comparación de Algoritmos: Permite comparar diferentes algoritmos y elegir el más eficiente para un problema dado.
Escalabilidad: Ayuda a predecir cómo se comportará un algoritmo cuando la cantidad de datos aumenta.

3. Análisis de Complejidad

Peor Caso: Se refiere al escenario donde el algoritmo tarda más tiempo o usa más recursos. Big O generalmente se refiere a este caso.
Mejor Caso y Caso Promedio: Aunque son importantes, se utilizan menos frecuentemente para la notación Big O.

4. Espacio vs. Tiempo

Complejidad Temporal: Se refiere al tiempo que tarda un algoritmo en ejecutarse.
Complejidad Espacial: Se refiere a la cantidad de memoria adicional que utiliza. Puede tener notaciones como O(1) (espacio constante) o O(n) (espacio lineal).

Ejemplo:


<span>import</span> <span>timeit</span>
<span>import</span> <span>matplotlib.pyplot</span> <span>as</span> <span>plt</span>
<span>import</span> <span>cProfile</span>
<span># O(1) </span>
<span>def</span> <span>constant_time_operation</span><span>():</span>
    <span>return</span> <span>42</span>
<span># O(log n) </span>
<span>def</span> <span>logarithmic_time_operation</span><span>(</span><span>n</span><span>):</span>
    <span>count</span> <span>=</span> <span>0</span>
    <span>while</span> <span>n</span> <span>></span> <span>1</span><span>:</span>
        <span>n</span> <span>//=</span> <span>2</span>
        <span>count</span> <span>+=</span> <span>1</span>
    <span>return</span> <span>count</span>
<span># O(n) </span>
<span>def</span> <span>linear_time_operation</span><span>(</span><span>n</span><span>):</span>
    <span>total</span> <span>=</span> <span>0</span>
    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>):</span>
        <span>total</span> <span>+=</span> <span>i</span>
    <span>return</span> <span>total</span>
<span># O(n log n) </span>
<span>def</span> <span>linear_logarithmic_time_operation</span><span>(</span><span>n</span><span>):</span>
    <span>if</span> <span>n</span> <span><=</span> <span>1</span><span>:</span>
        <span>return</span> <span>n</span>
    <span>else</span><span>:</span>
        <span>return</span> <span>linear_logarithmic_time_operation</span><span>(</span><span>n</span> <span>-</span> <span>1</span><span>)</span> <span>+</span> <span>n</span>
<span># O(n^2) </span>
<span>def</span> <span>quadratic_time_operation</span><span>(</span><span>n</span><span>):</span>
    <span>total</span> <span>=</span> <span>0</span>
    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>):</span>
        <span>for</span> <span>j</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>):</span>
            <span>total</span> <span>+=</span> <span>i</span> <span>+</span> <span>j</span>
    <span>return</span> <span>total</span>
<span># O(2^n) </span>
<span>def</span> <span>exponential_time_operation</span><span>(</span><span>n</span><span>):</span>
    <span>if</span> <span>n</span> <span><=</span> <span>1</span><span>:</span>
        <span>return</span> <span>1</span>
    <span>else</span><span>:</span>
        <span>return</span> <span>exponential_time_operation</span><span>(</span><span>n</span> <span>-</span> <span>1</span><span>)</span> <span>+</span> <span>exponential_time_operation</span><span>(</span><span>n</span> <span>-</span> <span>1</span><span>)</span>
<span># O(n!) </span>
<span>def</span> <span>factorial_time_operation</span><span>(</span><span>n</span><span>):</span>
    <span>if</span> <span>n</span> <span>==</span> <span>0</span><span>:</span>
        <span>return</span> <span>1</span>
    <span>else</span><span>:</span>
        <span>return</span> <span>n</span> <span>*</span> <span>factorial_time_operation</span><span>(</span><span>n</span> <span>-</span> <span>1</span><span>)</span>
<span># Function to measure execution time using timeit </span>
<span>def</span> <span>measure_time</span><span>(</span><span>func</span><span>,</span> <span>*</span><span>args</span><span>):</span>
    <span>execution_time</span> <span>=</span> <span>timeit</span><span>.</span><span>timeit</span><span>(</span><span>lambda</span><span>:</span> <span>func</span><span>(</span><span>*</span><span>args</span><span>),</span> <span>number</span><span>=</span><span>1000</span><span>)</span>
    <span>return</span> <span>execution_time</span>
<span>def</span> <span>plot_results</span><span>(</span><span>results</span><span>):</span>
    <span>functions</span><span>,</span> <span>times</span> <span>=</span> <span>zip</span><span>(</span><span>*</span><span>results</span><span>)</span>
    <span>colors</span> <span>=</span> <span>[</span><span>'</span><span>skyblue</span><span>'</span><span>,</span> <span>'</span><span>orange</span><span>'</span><span>,</span> <span>'</span><span>green</span><span>'</span><span>,</span> <span>'</span><span>red</span><span>'</span><span>,</span> <span>'</span><span>purple</span><span>'</span><span>,</span> <span>'</span><span>brown</span><span>'</span><span>,</span> <span>'</span><span>pink</span><span>'</span><span>]</span>
    <span>plt</span><span>.</span><span>figure</span><span>(</span><span>figsize</span><span>=</span><span>(</span><span>14</span><span>,</span> <span>8</span><span>))</span>
    <span>plt</span><span>.</span><span>bar</span><span>(</span><span>functions</span><span>,</span> <span>times</span><span>,</span> <span>color</span><span>=</span><span>colors</span><span>)</span>
    <span>for</span> <span>i</span><span>,</span> <span>v</span> <span>in</span> <span>enumerate</span><span>(</span><span>times</span><span>):</span>
        <span>plt</span><span>.</span><span>text</span><span>(</span><span>i</span><span>,</span> <span>v</span> <span>+</span> <span>0.5</span><span>,</span> <span>f</span><span>"</span><span>{</span><span>v</span><span>:</span><span>.</span><span>6</span><span>f</span><span>}</span><span>"</span><span>,</span> <span>ha</span><span>=</span><span>'</span><span>center</span><span>'</span><span>,</span>
                 <span>va</span><span>=</span><span>'</span><span>bottom</span><span>'</span><span>,</span> <span>rotation</span><span>=</span><span>0</span><span>,</span> <span>color</span><span>=</span><span>'</span><span>black</span><span>'</span><span>)</span>
    <span>plt</span><span>.</span><span>xlabel</span><span>(</span><span>'</span><span>Function Complexity</span><span>'</span><span>)</span>
    <span>plt</span><span>.</span><span>ylabel</span><span>(</span><span>'</span><span>Average Time (s)</span><span>'</span><span>)</span>
    <span>plt</span><span>.</span><span>title</span><span>(</span><span>'</span><span>Execution Time of Different Algorithm Complexities</span><span>'</span><span>)</span>
    <span>plt</span><span>.</span><span>grid</span><span>(</span><span>axis</span><span>=</span><span>'</span><span>y</span><span>'</span><span>,</span> <span>linestyle</span><span>=</span><span>'</span><span>--</span><span>'</span><span>,</span> <span>linewidth</span><span>=</span><span>0.5</span><span>,</span> <span>color</span><span>=</span><span>'</span><span>gray</span><span>'</span><span>,</span> <span>alpha</span><span>=</span><span>0.5</span><span>)</span>
    <span>plt</span><span>.</span><span>tight_layout</span><span>()</span>
    <span>plt</span><span>.</span><span>show</span><span>()</span>
<span>def</span> <span>main</span><span>():</span>
    <span>results</span> <span>=</span> <span>[]</span>
    <span>results</span><span>.</span><span>append</span><span>((</span><span>"</span><span>O(1)</span><span>"</span><span>,</span> <span>measure_time</span><span>(</span><span>constant_time_operation</span><span>)))</span>
    <span>results</span><span>.</span><span>append</span><span>((</span><span>"</span><span>O(log n)</span><span>"</span><span>,</span> <span>measure_time</span><span>(</span><span>logarithmic_time_operation</span><span>,</span> <span>10</span><span>)))</span>
    <span>results</span><span>.</span><span>append</span><span>((</span><span>"</span><span>O(n)</span><span>"</span><span>,</span> <span>measure_time</span><span>(</span><span>linear_time_operation</span><span>,</span> <span>10</span><span>)))</span>
    <span>results</span><span>.</span><span>append</span><span>((</span><span>"</span><span>O(n log n)</span><span>"</span><span>,</span> <span>measure_time</span><span>(</span>
        <span>linear_logarithmic_time_operation</span><span>,</span> <span>10</span><span>)))</span>
    <span>results</span><span>.</span><span>append</span><span>((</span><span>"</span><span>O(n^2)</span><span>"</span><span>,</span> <span>measure_time</span><span>(</span><span>quadratic_time_operation</span><span>,</span> <span>7</span><span>)))</span>
    <span>results</span><span>.</span><span>append</span><span>((</span><span>"</span><span>O(2^n)</span><span>"</span><span>,</span> <span>measure_time</span><span>(</span><span>exponential_time_operation</span><span>,</span> <span>7</span><span>)))</span>
    <span>results</span><span>.</span><span>append</span><span>((</span><span>"</span><span>O(n!)</span><span>"</span><span>,</span> <span>measure_time</span><span>(</span><span>factorial_time_operation</span><span>,</span> <span>112</span><span>)))</span>
    <span>plot_results</span><span>(</span><span>results</span><span>)</span>
<span>if</span> <span>__name__</span> <span>==</span> <span>'</span><span>__main__</span><span>'</span><span>:</span>
    <span>cProfile</span><span>.</span><span>run</span><span>(</span><span>"</span><span>main()</span><span>"</span><span>,</span> <span>sort</span><span>=</span><span>"</span><span>totime</span><span>"</span><span>,</span> <span>filename</span><span>=</span><span>"</span><span>output_profile.prof</span><span>"</span><span>)</span>
<span>import</span> <span>timeit</span>
<span>import</span> <span>matplotlib.pyplot</span> <span>as</span> <span>plt</span>
<span>import</span> <span>cProfile</span>

<span># O(1) </span>

<span>def</span> <span>constant_time_operation</span><span>():</span>
    <span>return</span> <span>42</span>

<span># O(log n) </span>

<span>def</span> <span>logarithmic_time_operation</span><span>(</span><span>n</span><span>):</span>
    <span>count</span> <span>=</span> <span>0</span>
    <span>while</span> <span>n</span> <span>></span> <span>1</span><span>:</span>
        <span>n</span> <span>//=</span> <span>2</span>
        <span>count</span> <span>+=</span> <span>1</span>
    <span>return</span> <span>count</span>

<span># O(n) </span>

<span>def</span> <span>linear_time_operation</span><span>(</span><span>n</span><span>):</span>
    <span>total</span> <span>=</span> <span>0</span>
    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>):</span>
        <span>total</span> <span>+=</span> <span>i</span>
    <span>return</span> <span>total</span>

<span># O(n log n) </span>

<span>def</span> <span>linear_logarithmic_time_operation</span><span>(</span><span>n</span><span>):</span>
    <span>if</span> <span>n</span> <span><=</span> <span>1</span><span>:</span>
        <span>return</span> <span>n</span>
    <span>else</span><span>:</span>
        <span>return</span> <span>linear_logarithmic_time_operation</span><span>(</span><span>n</span> <span>-</span> <span>1</span><span>)</span> <span>+</span> <span>n</span>

<span># O(n^2) </span>

<span>def</span> <span>quadratic_time_operation</span><span>(</span><span>n</span><span>):</span>
    <span>total</span> <span>=</span> <span>0</span>
    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>):</span>
        <span>for</span> <span>j</span> <span>in</span> <span>range</span><span>(</span><span>n</span><span>):</span>
            <span>total</span> <span>+=</span> <span>i</span> <span>+</span> <span>j</span>
    <span>return</span> <span>total</span>

<span># O(2^n) </span>

<span>def</span> <span>exponential_time_operation</span><span>(</span><span>n</span><span>):</span>
    <span>if</span> <span>n</span> <span><=</span> <span>1</span><span>:</span>
        <span>return</span> <span>1</span>
    <span>else</span><span>:</span>
        <span>return</span> <span>exponential_time_operation</span><span>(</span><span>n</span> <span>-</span> <span>1</span><span>)</span> <span>+</span> <span>exponential_time_operation</span><span>(</span><span>n</span> <span>-</span> <span>1</span><span>)</span>

<span># O(n!) </span>

<span>def</span> <span>factorial_time_operation</span><span>(</span><span>n</span><span>):</span>
    <span>if</span> <span>n</span> <span>==</span> <span>0</span><span>:</span>
        <span>return</span> <span>1</span>
    <span>else</span><span>:</span>
        <span>return</span> <span>n</span> <span>*</span> <span>factorial_time_operation</span><span>(</span><span>n</span> <span>-</span> <span>1</span><span>)</span>

<span># Function to measure execution time using timeit </span>
<span>def</span> <span>measure_time</span><span>(</span><span>func</span><span>,</span> <span>*</span><span>args</span><span>):</span>
    <span>execution_time</span> <span>=</span> <span>timeit</span><span>.</span><span>timeit</span><span>(</span><span>lambda</span><span>:</span> <span>func</span><span>(</span><span>*</span><span>args</span><span>),</span> <span>number</span><span>=</span><span>1000</span><span>)</span>
    <span>return</span> <span>execution_time</span>


<span>def</span> <span>plot_results</span><span>(</span><span>results</span><span>):</span>
    <span>functions</span><span>,</span> <span>times</span> <span>=</span> <span>zip</span><span>(</span><span>*</span><span>results</span><span>)</span>

    <span>colors</span> <span>=</span> <span>[</span><span>'</span><span>skyblue</span><span>'</span><span>,</span> <span>'</span><span>orange</span><span>'</span><span>,</span> <span>'</span><span>green</span><span>'</span><span>,</span> <span>'</span><span>red</span><span>'</span><span>,</span> <span>'</span><span>purple</span><span>'</span><span>,</span> <span>'</span><span>brown</span><span>'</span><span>,</span> <span>'</span><span>pink</span><span>'</span><span>]</span>
    <span>plt</span><span>.</span><span>figure</span><span>(</span><span>figsize</span><span>=</span><span>(</span><span>14</span><span>,</span> <span>8</span><span>))</span>
    <span>plt</span><span>.</span><span>bar</span><span>(</span><span>functions</span><span>,</span> <span>times</span><span>,</span> <span>color</span><span>=</span><span>colors</span><span>)</span>

    <span>for</span> <span>i</span><span>,</span> <span>v</span> <span>in</span> <span>enumerate</span><span>(</span><span>times</span><span>):</span>
        <span>plt</span><span>.</span><span>text</span><span>(</span><span>i</span><span>,</span> <span>v</span> <span>+</span> <span>0.5</span><span>,</span> <span>f</span><span>"</span><span>{</span><span>v</span><span>:</span><span>.</span><span>6</span><span>f</span><span>}</span><span>"</span><span>,</span> <span>ha</span><span>=</span><span>'</span><span>center</span><span>'</span><span>,</span>
                 <span>va</span><span>=</span><span>'</span><span>bottom</span><span>'</span><span>,</span> <span>rotation</span><span>=</span><span>0</span><span>,</span> <span>color</span><span>=</span><span>'</span><span>black</span><span>'</span><span>)</span>

    <span>plt</span><span>.</span><span>xlabel</span><span>(</span><span>'</span><span>Function Complexity</span><span>'</span><span>)</span>
    <span>plt</span><span>.</span><span>ylabel</span><span>(</span><span>'</span><span>Average Time (s)</span><span>'</span><span>)</span>
    <span>plt</span><span>.</span><span>title</span><span>(</span><span>'</span><span>Execution Time of Different Algorithm Complexities</span><span>'</span><span>)</span>
    <span>plt</span><span>.</span><span>grid</span><span>(</span><span>axis</span><span>=</span><span>'</span><span>y</span><span>'</span><span>,</span> <span>linestyle</span><span>=</span><span>'</span><span>--</span><span>'</span><span>,</span> <span>linewidth</span><span>=</span><span>0.5</span><span>,</span> <span>color</span><span>=</span><span>'</span><span>gray</span><span>'</span><span>,</span> <span>alpha</span><span>=</span><span>0.5</span><span>)</span>

    <span>plt</span><span>.</span><span>tight_layout</span><span>()</span>
    <span>plt</span><span>.</span><span>show</span><span>()</span>


<span>def</span> <span>main</span><span>():</span>
    <span>results</span> <span>=</span> <span>[]</span>
    <span>results</span><span>.</span><span>append</span><span>((</span><span>"</span><span>O(1)</span><span>"</span><span>,</span> <span>measure_time</span><span>(</span><span>constant_time_operation</span><span>)))</span>
    <span>results</span><span>.</span><span>append</span><span>((</span><span>"</span><span>O(log n)</span><span>"</span><span>,</span> <span>measure_time</span><span>(</span><span>logarithmic_time_operation</span><span>,</span> <span>10</span><span>)))</span>
    <span>results</span><span>.</span><span>append</span><span>((</span><span>"</span><span>O(n)</span><span>"</span><span>,</span> <span>measure_time</span><span>(</span><span>linear_time_operation</span><span>,</span> <span>10</span><span>)))</span>
    <span>results</span><span>.</span><span>append</span><span>((</span><span>"</span><span>O(n log n)</span><span>"</span><span>,</span> <span>measure_time</span><span>(</span>
        <span>linear_logarithmic_time_operation</span><span>,</span> <span>10</span><span>)))</span>
    <span>results</span><span>.</span><span>append</span><span>((</span><span>"</span><span>O(n^2)</span><span>"</span><span>,</span> <span>measure_time</span><span>(</span><span>quadratic_time_operation</span><span>,</span> <span>7</span><span>)))</span>
    <span>results</span><span>.</span><span>append</span><span>((</span><span>"</span><span>O(2^n)</span><span>"</span><span>,</span> <span>measure_time</span><span>(</span><span>exponential_time_operation</span><span>,</span> <span>7</span><span>)))</span>
    <span>results</span><span>.</span><span>append</span><span>((</span><span>"</span><span>O(n!)</span><span>"</span><span>,</span> <span>measure_time</span><span>(</span><span>factorial_time_operation</span><span>,</span> <span>112</span><span>)))</span>

    <span>plot_results</span><span>(</span><span>results</span><span>)</span>


<span>if</span> <span>__name__</span> <span>==</span> <span>'</span><span>__main__</span><span>'</span><span>:</span>
    <span>cProfile</span><span>.</span><span>run</span><span>(</span><span>"</span><span>main()</span><span>"</span><span>,</span> <span>sort</span><span>=</span><span>"</span><span>totime</span><span>"</span><span>,</span> <span>filename</span><span>=</span><span>"</span><span>output_profile.prof</span><span>"</span><span>)</span>
import timeit
import matplotlib.pyplot as plt
import cProfile

# O(1) 

def constant_time_operation():
    return 42

# O(log n) 

def logarithmic_time_operation(n):
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count

# O(n) 

def linear_time_operation(n):
    total = 0
    for i in range(n):
        total += i
    return total

# O(n log n) 

def linear_logarithmic_time_operation(n):
    if n <= 1:
        return n
    else:
        return linear_logarithmic_time_operation(n - 1) + n

# O(n^2) 

def quadratic_time_operation(n):
    total = 0
    for i in range(n):
        for j in range(n):
            total += i + j
    return total

# O(2^n) 

def exponential_time_operation(n):
    if n <= 1:
        return 1
    else:
        return exponential_time_operation(n - 1) + exponential_time_operation(n - 1)

# O(n!) 

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

# Function to measure execution time using timeit 
def measure_time(func, *args):
    execution_time = timeit.timeit(lambda: func(*args), number=1000)
    return execution_time


def plot_results(results):
    functions, times = zip(*results)

    colors = ['skyblue', 'orange', 'green', 'red', 'purple', 'brown', 'pink']
    plt.figure(figsize=(14, 8))
    plt.bar(functions, times, color=colors)

    for i, v in enumerate(times):
        plt.text(i, v + 0.5, f"{v:.6f}", ha='center',
                 va='bottom', rotation=0, color='black')

    plt.xlabel('Function Complexity')
    plt.ylabel('Average Time (s)')
    plt.title('Execution Time of Different Algorithm Complexities')
    plt.grid(axis='y', linestyle='--', linewidth=0.5, color='gray', alpha=0.5)

    plt.tight_layout()
    plt.show()


def main():
    results = []
    results.append(("O(1)", measure_time(constant_time_operation)))
    results.append(("O(log n)", measure_time(logarithmic_time_operation, 10)))
    results.append(("O(n)", measure_time(linear_time_operation, 10)))
    results.append(("O(n log n)", measure_time(
        linear_logarithmic_time_operation, 10)))
    results.append(("O(n^2)", measure_time(quadratic_time_operation, 7)))
    results.append(("O(2^n)", measure_time(exponential_time_operation, 7)))
    results.append(("O(n!)", measure_time(factorial_time_operation, 112)))

    plot_results(results)


if __name__ == '__main__':
    cProfile.run("main()", sort="totime", filename="output_profile.prof")

Enter fullscreen mode Exit fullscreen mode

Recordar que no solo basta con aplicar notación big o si bien este es el primer paso existe otras formas de optimizar en memoria ejemplo el uso de slots, cache, hilos, paralelismo, procesos etc.

Gracias por leer !!
Apóyame reaccionando e opinando.

原文链接：Notación Big O – Python

展开阅读全文

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END