[SER222] Characterizing Algorithms (5/5): Analysis Approaches
Summary
TLDREn 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
💻 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.
🧠 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.
Mindmap
Keywords
💡Función de crecimiento
💡Enfoque analítico
💡Enfoque empírico
💡Asignación
💡Bucle for
💡Operación de comparación
💡Complejidad temporal
💡Big O
💡Iterador
💡Caja negra
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.
浏览更多相关视频
Enfoques de investigación cuantitativo y cualitativo
[SER222] Analytical Analysis (4/5): Analysis of ThreeSum
[SER222] Empirical Analysis (1/8): The Empirical Process
Which Sales Strategy Is Best For Your Startup?
CURSO Networking y Marketing Personal: Competencias directivas |5.1 Qué es networking online-offline
robot 12
5.0 / 5 (0 votes)