[SER222] Characterizing Algorithms (5/5): Analysis Approaches

Summary

En este video, se exploran dos enfoques para analizar cómo actúa un programa: el enfoque analítico y el empírico. El analítico examina el código línea por línea para generar una función de crecimiento exacta, pero es laborioso y toma tiempo. El empírico, por otro lado, mide el rendimiento del programa mediante la ejecución en diferentes entradas, proporcionando una aproximación más rápida, pero menos precisa. Ambos enfoques tienen sus ventajas y desventajas. Se discutirán ambos métodos con más detalle en futuras secciones del curso.

Takeaways

• 🖥️ La función de crecimiento analiza cómo un programa actúa en función del número de operaciones que realiza.
• 📊 En el pasado, se ha solicitado escribir una función de crecimiento basada en la cantidad de operaciones de un código.
• 🔄 El ejemplo de código presentado crea un array y lo llena con datos aleatorios utilizando un bucle `for`.
• 📈 El objetivo es escribir una función de crecimiento que indique cuántos pasos toma el código en función del tamaño de la entrada.
• 📝 La aproximación analítica examina cada línea del código para contar el número exacto de operaciones que se ejecutan.
• ⏳ Una desventaja de la aproximación analítica es que consume mucho tiempo, especialmente para programas largos.
• 🧪 La aproximación empírica se basa en observar cuánto tarda un programa en ejecutarse con diferentes tamaños de entrada.
• 📉 La aproximación empírica es más rápida, pero no garantiza una respuesta exacta y solo ofrece una aproximación.
• ⚖️ Ambas aproximaciones tienen ventajas y desventajas: la analítica es precisa pero lenta, y la empírica es rápida pero menos exacta.
• 📚 En próximas secciones, se profundizará en ambas aproximaciones para analizar algoritmos de manera efectiva.

Q & A

¿Qué enfoque se menciona en el video para analizar cómo actúa un programa?

Se mencionan dos enfoques principales: el enfoque analítico y el enfoque empírico.

¿Qué se busca lograr con una función de crecimiento en la programación?

Se busca estimar cuántos pasos o operaciones tomará un código en función del tamaño de la entrada, ayudando a comprender su eficiencia.

¿Cómo se calcula el número de operaciones dentro de un bucle 'for' según el enfoque analítico?

Se cuenta cuántas veces se ejecutan las operaciones dentro del bucle. En este caso, el bucle se ejecuta N veces, por lo que la operación interna también se ejecutará N veces.

¿Qué ventaja principal ofrece el enfoque analítico al analizar algoritmos?

La principal ventaja es que proporciona una respuesta exacta al analizar cada línea del código de manera detallada.

¿Cuáles son las desventajas del enfoque analítico?

Las desventajas incluyen el tiempo requerido para analizar código complejo y la dificultad de obtener respuestas precisas sobre el tiempo de ejecución.

¿En qué consiste el enfoque empírico para analizar un algoritmo?

El enfoque empírico consiste en ejecutar el programa con diferentes tamaños de entrada y observar el tiempo que toma, para luego inferir una función de crecimiento basada en esos resultados.

¿Qué ventaja ofrece el enfoque empírico sobre el analítico?

El enfoque empírico es mucho más rápido de aplicar, ya que no requiere analizar línea por línea, sino solo ejecutar el programa y medir los resultados.

¿Cuál es la desventaja principal del enfoque empírico?

Su desventaja es que se basa en aproximaciones y existe la posibilidad de que algunos inputs no probados puedan generar comportamientos inesperados.

¿Por qué el enfoque empírico se considera más práctico en programas grandes?

Porque en programas grandes, analizar línea por línea usando el enfoque analítico puede ser extremadamente laborioso y consumir mucho tiempo.

¿Cómo se relacionan los enfoques empírico y analítico con el concepto de 'caja negra'?

En el enfoque empírico, se trata al código como una 'caja negra', es decir, se ignoran los detalles internos y solo se observan los resultados. En el enfoque analítico, se analiza cada línea de código para entender completamente su comportamiento.

Outlines

00:00

💻 Análisis de algoritmos mediante funciones de crecimiento

En este párrafo, se introduce el análisis de algoritmos y cómo se puede usar una función de crecimiento para medir la cantidad de operaciones que realiza un código. Se usa un fragmento de código simple que llena un arreglo con datos aleatorios mediante un bucle for, y se describe el proceso de contar las operaciones: desde la asignación inicial, la configuración de la variable del iterador, hasta las comparaciones y la cantidad de veces que se ejecuta el bucle. El objetivo es calcular una función de crecimiento que muestre cuántos pasos tomará el algoritmo dependiendo del tamaño de la entrada.

05:02

🧠 Simplificación de funciones de crecimiento

Aquí se detalla cómo simplificar una función de crecimiento, reduciendo una expresión compleja a una lineal. Aunque el código parece simple, su análisis revela que contiene cinco términos en la función de crecimiento. Se explica cómo cada operación en el código contribuye al tiempo de ejecución, y cómo estas operaciones se deben contar con precisión para calcular cuántos pasos toma el algoritmo. Se menciona también la posibilidad de estimar directamente cuánto tiempo tomará el código, no solo cuántas operaciones realiza.

📊 Introducción al enfoque empírico en el análisis de algoritmos

Se introduce el análisis empírico como una alternativa al análisis analítico. En lugar de examinar el código línea por línea, el enfoque empírico consiste en ejecutar el código con diferentes tamaños de entrada y medir el tiempo que toma para inferir una función de crecimiento. Este enfoque es más rápido y práctico, pero no garantiza precisión absoluta. A través de pruebas de tiempo en diferentes tamaños de arreglos, se puede aproximar cómo crece el tiempo de ejecución con respecto a la entrada, tratándose el código como una 'caja negra'.

⚖️ Comparación entre el análisis empírico y analítico

Este párrafo compara las ventajas y desventajas de los enfoques analítico y empírico. El análisis analítico es más preciso porque examina cada línea de código, pero es lento y difícil de aplicar a programas grandes. Por otro lado, el análisis empírico es más rápido y fácil, pero solo proporciona aproximaciones basadas en las entradas probadas, dejando espacio para comportamientos inesperados con entradas no probadas. Se resalta que el análisis analítico da respuestas exactas, mientras que el empírico ofrece una visión más aproximada basada en la evidencia.

⏱️ Profundización en las ventajas y desventajas de ambos enfoques

Aquí se discuten más a fondo las fortalezas y debilidades de ambos enfoques. Se destaca que el análisis empírico permite obtener resultados rápidamente y es más fácil de aplicar, mientras que el analítico, aunque es más exacto, puede ser extremadamente laborioso y difícil de ejecutar correctamente. También se menciona la dificultad de medir tiempos extremadamente pequeños en el análisis analítico, lo que puede hacer que ciertos resultados parezcan irrelevantes o poco prácticos. En resumen, ambos enfoques tienen su lugar dependiendo del tipo de análisis que se quiera realizar.

Keywords

💡Función de crecimiento

Una función de crecimiento describe cómo cambia la cantidad de operaciones realizadas por un programa a medida que aumenta el tamaño de la entrada. En el video, se muestra cómo se puede calcular esta función analizando línea por línea el código, y se utiliza un ejemplo de un bucle que llena una matriz con elementos aleatorios. Esta función permite predecir el tiempo necesario para ejecutar un programa a medida que aumenta el tamaño de los datos.

💡Enfoque analítico

El enfoque analítico implica examinar directamente el código fuente para contar el número exacto de operaciones que realiza. Se utiliza para obtener una solución exacta sobre cuántas operaciones realizará un programa según su tamaño de entrada. En el video, se menciona que aunque este enfoque ofrece una precisión absoluta, puede ser muy lento y tedioso para grandes cantidades de código.

💡Enfoque empírico

Este enfoque consiste en ejecutar el programa con diferentes tamaños de entrada y medir el tiempo de ejecución para inferir una función de crecimiento. Es una aproximación que trata al código como una 'caja negra', ignorando los detalles internos y basándose únicamente en la observación del comportamiento. En el video, se destaca que este enfoque es más rápido que el analítico, pero puede no capturar comportamientos inesperados.

💡Asignación

La asignación es el acto de dar un valor a una variable. En el video, se menciona que una de las primeras operaciones en el código es una asignación, que se contabiliza como una operación en la función de crecimiento. Es un concepto clave al analizar el número de operaciones básicas en un programa.

💡Bucle for

Un bucle for es una estructura de control que repite un bloque de código un número específico de veces. En el video, el bucle se utiliza para llenar una matriz con elementos aleatorios, y se analiza cómo cada iteración del bucle implica varias operaciones (como la asignación y la comparación). Este tipo de bucles es fundamental para determinar la complejidad temporal de un algoritmo.

💡Operación de comparación

Una comparación verifica una condición, como en el bucle for, donde se comprueba si el índice ha alcanzado un cierto valor. En el video, se menciona que esta operación se realiza N+1 veces, siendo N el número de elementos en la matriz. La cantidad de comparaciones es crucial para entender cómo crece el número de operaciones con el tamaño de los datos.

💡Complejidad temporal

La complejidad temporal describe cuánto tiempo toma ejecutar un algoritmo en función del tamaño de la entrada. En el video, se explora cómo calcular esta complejidad utilizando la función de crecimiento, y se menciona que diferentes enfoques (analítico y empírico) pueden ayudar a determinar el tiempo que tomará el programa.

💡Big O

Big O es una notación matemática que describe el peor caso de crecimiento de un algoritmo en función de su tamaño de entrada. Aunque no se menciona en detalle en el video, se alude a cómo el análisis analítico puede ayudarnos a determinar el Big O de un código, proporcionando una estimación de la eficiencia del algoritmo.

💡Iterador

Un iterador es una variable que cambia su valor en cada repetición de un bucle. En el video, se analiza cómo la inicialización y el incremento de un iterador forman parte de las operaciones que se cuentan para la función de crecimiento. El iterador es esencial para controlar cuántas veces se ejecuta un bucle.

💡Caja negra

La metáfora de la 'caja negra' se refiere a tratar un sistema sin conocer su funcionamiento interno. En el enfoque empírico descrito en el video, se trata al código como una caja negra, donde solo se observan los resultados (tiempo de ejecución) para inferir el comportamiento del programa, sin examinar directamente el código.

Highlights

Introduction of two approaches to analyzing how a program acts: analytical and empirical.

Analytical approach involves breaking down the code line by line to count operations and determine a growth function.

In the analytical example, the for-loop is analyzed with N + 1 comparisons and N increments.

The goal of the analytical approach is to derive a growth function that describes the code’s behavior based on input size.

The analytical approach provides an exact solution but can be time-consuming, especially for larger codebases.

Empirical approach treats the program as a black box, running it with different inputs and observing the results.

With the empirical approach, growth functions are inferred based on evidence from test runs with varying input sizes.

The empirical approach is faster but relies on approximation, which could miss edge cases or unexpected behaviors.

The analytical approach is advantageous because it provides an exact answer and eliminates unexpected behaviors.

A disadvantage of the analytical approach is the difficulty of getting accurate time estimates for small operations.

The empirical approach is easier to apply and allows for quicker analysis, often leading to results in a shorter time.

A disadvantage of the empirical approach is that it only provides evidence for the inputs tested, leaving the possibility of unseen behaviors with other inputs.

In empirical analysis, if a wide range of test inputs is used, a better understanding of the function’s behavior can be obtained.

The balance between analytical and empirical approaches depends on the specific context of the algorithm and the available resources.

The video concludes with the promise to explore both analytical and empirical approaches in detail in upcoming sections.

Transcripts

In this video, I want to discuss different approaches

to analyzing how a program acts, right?

How to characterize it.

So in the past, you often, you should have

been asked to write what is call a growth function

from a piece of code, so here you can see

I just have some sample code,

which basically is set up to create an array

And populate it all with these different,

random pieces of data.

It's just a simple for-loop, it's only three lines,

very straight forward.

So, what you may have done in the past is looked at a bit,

a bit of code like this and gone line by line

and try to figure out how many operations that take place.

So, you know, first thing up there we have maybe,

well see, that's one line, it's an assignment,

but there's actually a couple things happening there,

but we can just say, "Hey that's just, you know,

it's assignment, it's one operations,"

we'll say that's one.

And then, you know, we have the for-loop

and there's one thing inside of it and I'll have to go then

and analyze my for-loop and decide

basically how many operations it contains, right?

Our goal, right, in the end will basically be

to write a growth function which,

I have actually down there right?

On the counts of exactly how many steps

this piece of code will take if I have a certain size input.

And the size of input here, right, is basically

how many random elements are going to be in my array.

So looking at our example, we have, for example,

in our growth function our value over here of one.

And the one is coming from this first line, right?

Our assignment, that's one thing that's happening.

Then looking my for-loop, well,

the first thing that happens in the for-loop

is I need to basically set up my iterator variable.

So that's going to be take one operation.

So that's where this one over here is coming from.

Alright, and that is representing this bit over here.

Then I have that, that check where I basically just see,

am I done with this loop or not?

And, well, it's a little bit annoying,

but basically this is going to take N plus one of,

well this is going to run N plus one times.

Because you have N checks, right?

'Cause it's gonna increment N times, and then, right?

There's the final check where it's like,

"Oh it's going to return false,"

and the loop levels it out, so it's always

just a little bit more.

So N plus one over here.

Right, and that is corresponding to how many times

that's going to be checked, right?

So, again I'm just counting the number of operations,

right, I'm counting over here,

where I had the number of equals, number of equals.

Over here I'm counting the number of comparisons.

Over here I have the incrementor

that's going to be executed N times

because it's going to go from zero to 100.

Or zero nine nine.

And so over here, I have N, right?

That's how many times the line's going to run.

Now that whole loop, right, that loop is going to run

based on that, on those bounds, right?

N number of times, right?

Based on the size of the pool, right?

Pool is the array we're populating stuff.

So if I think about, "Oh, what's going to run

inside of this," right?

That, that line inside this thing here,

right, this assignment, that will run as many times

as the whole loop runs, the whole loop runs N times,

so that thing is actually going to run N times itself.

And so even though I've just had three lines of code here,

right, notice I have a expression, right,

that has five terms in it.

So it took a little bit of time, and I can simplify it

so I can get basically a linear expression which tells me,

you know, for a size, for an input of this big a size,

how many operations will it take, right?

And those operations are a little bit mixed, right?

Some of them are equal, some of them are, are less than,

right, but it's the number of operations.

It tells me exactly how many things will happen.

Probably this is what you've done before.

So this is, this is great, because now I can tell, you know,

exactly how long this algorithm will take to run, right?

Hopefully I can have this idea of,

"Oh, an equal takes, you know, this amount of time,

less than takes this amount of time,"

and so I can actually even directly estimate how long

this function will take to run, right?

Not just the number of operations it'll take.

More in particular, import, but how long it'll take as well.

So that's very nice.

This is kind of an analytical approach.

We're looking directly at the code, right?

We're, we're examining what's in it, and we're writing

a growth function from what we see in there.

And there's actually some additional rules,

talking about a few of them.

But there's rules, basically, to directly figure out

what is the big O, right?

What is the growth function, excuse me,

of this bit of code, right?

There's rules to follow.

So this is analytical approach.

And it's really, it's nice if you can do it,

because it gives us an exact answer.

Unfortunately, there's also some problems with it.

So there's actually a second way that I now want to

introduce that we can use to analyze algorithms.

This is going to be an empirical approach using observation.

While the last approach we gave, right, analytical,

is very nice 'cause it gives us a perfect answer,

and exact solution, it generally just

takes too much time to do, right?

We had three lines of code there,

and you can imagine that if you have a program

where it was a hundred lines, you know,

you'll be there for a week trying to analyze it.

So that's, you know,

not something we really have time to do.

So the empirical approach goes like this,

we have that same snippet of code, but then let's try

running it on different sizes of inputs.

So maybe I run it on an array of size 10,

and it takes 20 seconds.

I run it on an array of size 20 and it takes 40 seconds.

Okay, I have basically some evidence

about how this thing acts.

And from that I can infer the growth functions so I can say,

"Hey, this thing probably grows like F of N equal two N,"

right, however many inputs I give it, right?

That times two is the number of seconds

this algorithm will take to run.

Alright, so in this case I'm treating my code

basically like a black box, right?

I'm ignoring the fact that there is, you know,

this first sign that creates an array,

there's a loop, right, that has a start, a finish, right?

An incrementor, you know there's stuff,

I'm ignoring all that, right?

It's just a black box, I'm just going to run it on

different inputs and I'm going to see what result

they give back to me.

And based on what I observe from those results,

I'll guess, or I'll approximate a growth function for it.

So this is generally a lot easier to do

because it takes less time, right?

I don't need to look at every single line of code.

So these are two approaches, right?

We can either take the analytical route,

which you've seen in previous courses,

or the empirical route.

We'll talk about both them in this class.

Now of course we should keep in mind that

there are different times we want to use these.

So let's think about the analytical approach.

What are some of the advantages of it?

Well, the main advantage, right,

is it gives us an exact answer.

Empirical, right, is ultimately an approximation, right?

Because we're not looking at every single line,

there's always a chance

that something unexpected could happen.

With an analytical approach, we would really go

and look at each line in our program

and figure out how it behaves.

So there's definitely gonna be no kind of character,

or no unexpected things that is, that are hidden from us,

right, there's no, no chance that something bad will happen.

That's the strong advantage of analytical.

Disadvantages, well, a disadvantage of analytical

is mainly the time it takes to do the analysis.

If I'll have a huge amount of code, right,

it'll take me forever to write that function.

Also, right, it's, well, it takes us time to write it,

it's also hard to get it to be correct,

and then if we want to do things like estimate time for it,

well, it can be very hard to do.

We have to basically go and search for

all these different little different constants

and figure out, you know,

how long does this operation take to run,

and sometimes, right, when you have operations

that are really quick, well, it's like,

"Oh you know these things take, you know, .0000001 seconds,"

right, and so it's like, well, you know,

does that really even make sense, right?

Those things are almost too small to measure.

So that's one of the downsides.

So, empirical, advantages of empirical,

it's easier to do, right?

It's kind of the flip side of analytical, right?

We can look at a function as a black box and hopefully,

right, just run it a few times, right?

And in an hour we'll have, you know, a graph,

or, you know, a picture of, of our different results

we got from our different size inputs

and from that we can guess how it acts, right?

So it's very, very much quicker, right,

for us to apply that.

Disadvantage of empirical, right,

is basically the flip side of the advantage for analytic,

right, so with the empirical, we have this issue of

"Oh, I've run it a bunch of different times

with these different inputs but, and I have evidence

where I know, you know, how did that function perform

for that particular input," but that's really just evidence,

right, so I know that it took 20 seconds for this input,

40 seconds for this other input,

but there are a million inputs that I did not try.

So maybe those will act similarly, right?

Maybe if I try an input of size 40, right,

it'll take 80 seconds, that'd be great,

But there's always that chance that there'll be some input

that invokes some unexpected behavior

and gives us something that's completely unexpected for us,

right, that's going to be a huge issue.

We don't get to see everything.

Now, if we do have kind of a good suit of tests, right?

If we, if we go and we probe

and check a whole bunch of different inputs

of that function, then we should have

some measure of certitude,

but it's not going to be guaranteed.

Alright, so those are our two approaches.

In our next sections we'll go into depth on how to do,

how to take both of those approaches

to analyze an algorithm.