[SER222] Analytical Analysis (1/5): Defining f(n)

Summary

El vídeo explica qué representa F de N en el análisis de crecimiento de funciones y cómo elegir el parámetro adecuado. Se discute la importancia de seleccionar una operación que ocurra con frecuencia y no dependa de condiciones lógicas para medir el comportamiento de un algoritmo con respecto al tamaño de la entrada. Se utiliza el ejemplo de la búsqueda binaria para ilustrar cómo elegir la operación correcta y se enfatiza la relevancia de las operaciones pesadas y su frecuencia en la función de crecimiento.

Takeaways

• 🔍 La función F(N) representa la función de crecimiento que mide la cantidad de trabajo que se necesita para ejecutar un algoritmo en función del tamaño de la entrada.
• 🕒 La notación T(N) se usó anteriormente para abreviar la cantidad de tiempo que se necesita para resolver un problema de tamaño N, pero F(N) busca ser más exacta.
• 📈 Los algoritmos eficientes tienen funciones de crecimiento que se incrementan lentamente a medida que el tamaño del problema aumenta.
• 💥 Los algoritmos poco eficientes tienen funciones de crecimiento que crecen rápidamente, lo que significa que el tiempo de ejecución aumenta dramáticamente con el tamaño de la entrada.
• 🛠 Para definir F(N) con precisión, es necesario elegir qué tipo de operación se está contando, ya que esto afecta significativamente la forma de la función de crecimiento.
• ⚖️ Es importante medir una operación que ocurra con frecuencia y no una que suceda solo una vez, ya que esto no nos daría una idea precisa del comportamiento del algoritmo.
• 📉 Las operaciones de bajo peso, como una adición o un desplazamiento de bits, pueden no ser lo suficientemente significativas para medir en la función de crecimiento.
• 🔄 En el análisis de algoritmos, se prefieren las operaciones que son parte del núcleo del algoritmo y que ocurran con regularidad.
• ❌ Se deben evitar las líneas de código que solo ocurren una vez o que están condicionadas por una lógica que no se puede predecir con facilidad.
• 🔍 Al analizar el código fuente de una búsqueda binaria, se debe considerar qué líneas son candidatas para medir en la función de crecimiento, teniendo en cuenta su frecuencia y relevancia en el algoritmo.

Q & A

¿Qué representa F de N en el contexto del vídeo?

F de N representa una función de crecimiento que mide directamente o exactamente algo, como el número de operaciones necesarias para ejecutar un algoritmo en una entrada de ese tamaño.

¿Cuál es la importancia de los análisis empíricos mencionados en el vídeo?

Los análisis empíricos se utilizan para entender cuánto tiempo se tarda en resolver un problema a medida que su tamaño aumenta, utilizando la notación T de N para representar esa cantidad de tiempo.

¿Qué tipo de funciones crece muy lentamente según se describe en el vídeo?

Las funciones que crecen muy lentamente son aquellas en las que, a medida que el tamaño del problema aumenta, el valor de F de N no cambia mucho, lo que indica que el algoritmo es bastante eficiente.

¿Cómo se determina si un algoritmo es eficiente según el vídeo?

Un algoritmo es eficiente si su función de crecimiento F de N no se dispara dramáticamente a medida que aumenta el tamaño del problema, lo que significa que no requiere un aumento desmedido de trabajo o tiempo para resolver el problema.

¿Qué es lo que se debe medir según el vídeo para definir una función de crecimiento?

Se debe medir una operación que sea frecuentemente ocurriendo, no constante en tiempo y que no esté bajo una expresión lógica o condición que dificulte su medición.

¿Por qué es importante elegir una operación pesada para medir según el vídeo?

Es importante elegir una operación pesada para medir porque si se está analizando la mayor parte del trabajo que se necesita hacer, entonces el análisis incluirá cualquier otra cosa que suceda en la función.

¿Qué es lo que se debe tener en cuenta al analizar un código para determinar qué operación medir?

Al analizar un código, se debe tener en cuenta encontrar una operación que suceda con frecuencia, no sea de tiempo constante, y que no esté bajo una expresión lógica que dificulte su medición.

¿Qué es lo que se debe evitar al medir una operación para la función de crecimiento en el código fuente del vídeo?

Se debe evitar medir operaciones que solo ocurran una vez, operaciones que tengan una dependencia de la entrada y operaciones que estén bajo condiciones lógicas que afecten su ejecución.

¿Cómo se determina la complejidad de tiempo de un algoritmo según el vídeo?

La complejidad de tiempo de un algoritmo se determina al analizar la operación que se ejecuta con mayor frecuencia y peso en el algoritmo, y ver cómo esa operación se ve afectada por el tamaño de la entrada.

¿Por qué es importante la elección de la operación correcta al medir la complejidad de un algoritmo?

La elección de la operación correcta es importante porque determina la precisión del análisis de la complejidad del algoritmo. Si se elige una operación que no se relacione directamente con el tamaño del problema o que no sea representativa del trabajo realizado por el algoritmo, el análisis podría ser incorrecto o no representativo.

Outlines

00:00

📊 Análisis de Funciones de Crecimiento en Algoritmos

El vídeo comienza explicando la importancia de las funciones de crecimiento (F de N) en la informática para entender cómo se comportan los algoritmos a medida que el tamaño del problema crece. Se menciona que en análisis empíricos, se usaba T de N para representar el tiempo que toma un algoritmo, pero ahora se busca una función más exacta que calcule directamente el número de operaciones necesarias para procesar un input de tamaño N. Se destaca que F de N puede variar mucho dependiendo del algoritmo; algunos crecen lentamente y son eficientes, mientras que otros crecen rápidamente y son menos eficientes. Además, se discute la necesidad de ser específico sobre qué operaciones se cuentan al analizar un algoritmo, ya que esto afecta directamente la forma de la función de crecimiento.

05:00

🔍 Cómo Seleccionar la Operación para Analizar en un Algoritmo

En este segundo párrafo, se profundiza en cómo elegir la operación adecuada para medir en un algoritmo. Se sugiere que se debe seleccionar una operación que ocurra con frecuencia y que no sea trivial, como una suma o un desplazamiento de bits, sino algo más complejo como intercambiar elementos en un array. Se enfatiza que aunque un algoritmo pueda tener muchas operaciones, lo importante es medir la que más peso tiene en el proceso general. Se utiliza el ejemplo del código fuente de una búsqueda binaria para ilustrar cómo se selecciona la operación a medir y cómo se evitan las que dependen de condiciones lógicas o que solo ocurren una vez.

10:03

🛠 Análisis Detallado del Código de Búsqueda Binaria

El tercer párrafo se centra en un análisis detallado del código de búsqueda binaria, identificando qué líneas son candidatas para medir en términos de su frecuencia y relevancia en el comportamiento del algoritmo. Se señala que las líneas que ocurren solo una vez o que están condicionadas por una lógica compleja deben evitarse. Se eligen para la medición las líneas que realizan comparaciones y cálculos dentro del bucle principal, ya que son operaciones que ocurren con frecuencia y están relacionadas con el tamaño del input. Se concluye con la importancia de ser cuidadoso al seleccionar las operaciones a medida para evitar complicaciones en el análisis de la eficiencia del algoritmo.

Keywords

💡F de N

F de N es una función de crecimiento que mide cómo cambia la cantidad de trabajo o tiempo necesario para ejecutar un algoritmo a medida que el tamaño del problema, representado por N, aumenta. En el video, se utiliza para analizar el rendimiento de algoritmos y determinar cuántas operaciones se requieren en función del tamaño del input.

💡Tamaño del problema

El tamaño del problema, representado por N, es una métrica clave que describe la cantidad de datos o la magnitud del input que un algoritmo debe procesar. En el video, se usa este concepto para explicar cómo varía el tiempo o las operaciones necesarias en un algoritmo, dependiendo de cuánto crezca el tamaño del problema.

💡Función de crecimiento

Una función de crecimiento calcula el número de operaciones necesarias para resolver un problema de cierto tamaño. Se utiliza para evaluar el comportamiento de un algoritmo a medida que aumenta la magnitud de los datos de entrada. En el video, las funciones de crecimiento son clave para comparar la eficiencia de diferentes algoritmos.

💡Análisis empírico

El análisis empírico es un método que evalúa el rendimiento de un algoritmo observando su comportamiento en la práctica, midiendo el tiempo o las operaciones necesarias en función del tamaño del problema. El video menciona este tipo de análisis como un punto de partida para discutir las funciones de crecimiento.

💡Operaciones

Las operaciones son las acciones básicas que un algoritmo realiza, como sumar, restar o comparar. En el video se explica que el tipo y número de operaciones influyen directamente en la función de crecimiento y, por lo tanto, en el tiempo de ejecución del algoritmo.

💡Algoritmo

Un algoritmo es un conjunto de instrucciones o pasos que se siguen para resolver un problema. En el contexto del video, se refiere a los procedimientos que se analizan utilizando funciones de crecimiento para determinar su eficiencia en función del tamaño del problema.

💡Big O

La notación Big O describe la eficiencia de un algoritmo en términos del peor de los casos, midiendo su comportamiento asintótico a medida que el tamaño del input crece. En el video se menciona que es crucial entender qué operaciones se están contando antes de determinar la notación Big O de un algoritmo.

💡Análisis del código

El análisis del código implica examinar el código fuente de un programa para identificar operaciones clave y su impacto en la eficiencia del algoritmo. En el video, se hace referencia a este análisis para identificar líneas de código que se deben considerar para medir su frecuencia y relevancia en el comportamiento del algoritmo.

💡Condicionales

Los condicionales, como las declaraciones if-else, son estructuras de control que determinan qué acciones tomar basándose en una condición. En el video, se explica que es difícil medir estas operaciones porque dependen del flujo del programa y no siempre ocurren, lo que afecta la precisión de las funciones de crecimiento.

💡Búsqueda binaria

La búsqueda binaria es un algoritmo eficiente que busca un elemento en una lista ordenada dividiendo repetidamente la lista en mitades. En el video, se utiliza como ejemplo de un algoritmo cuya función de crecimiento se puede analizar al contar operaciones clave como comparaciones y cálculos de índices medios.

Highlights

Discussing the concept of F of N and its representation of a growth function.

Explaining the empirical analysis and the use of T of N to represent time complexity.

Introducing the idea that growth functions aim to calculate something directly or exactly.

Growth functions take in problem size and return the number of operations needed for an algorithm.

The purpose of growth functions is to understand how work changes with increasing problem size.

Describing different growth functions and their implications for algorithm efficiency.

Highlighting that growth functions help determine how well an algorithm performs.

Explaining that growth functions are used to analyze operations needed to solve a given problem.

Discussing the need for precision in defining what F of N computes.

Pointing out that operations counted in growth functions should be frequently occurring and heavyweight.

Cautioning against counting operations that only happen once or are under conditional logic.

Stressing the importance of picking an operation that is indicative of the algorithm's overall complexity.

Providing an example of analyzing a binary search algorithm to determine which operations to count.

Explaining why certain lines of code in binary search are not suitable for growth function analysis.

Discussing the importance of understanding the dependency of operations on input size.

Concluding with a summary of how to select operations for growth function analysis in code.

Transcripts

- In this video I want to discuss

what exactly it is that F of N represents.

And also what is the meaning of the parameter.

All right, so in the previous section,

we talked mainly about this idea of an empirical analysis

where we had maybe N as being the size of a problem,

and then we used the notation T of N to represent

a function that abbreviated the amount of time.

And that's fine, but now in this section

what we really want to discuss

is this more exact idea of a growth function.

Now if you think back to the beginning,

a while ago when we introduced

some basic terminology of this section

we said that growth functions are functions

that are supposed to directly

or exactly calculate something.

Typically they calculate something like,

they take in basically a problem size,

for example the size of an array

and return how many operations are needed

in order to run that algorithm on that sized input.

The purpose of the growth function

is really is to basically say,

okay as a problem gets bigger and bigger and bigger

how does the amount of work I need to do

on that function change?

So some growth functions maybe look something like this,

where this is basically our N over here,

F of N is over here.

Sometimes it'll look like this, which is actually very nice

because as the problem size gets bigger,

really I'm not having to spend all that much more time

or work to solve that problem.

My F of N value doesn't change all that much,

that's very nice.

That's a function that grows very slowly

and it represents an algorithm that is pretty efficient.

For an example, we have a growth function

that looks like this.

This is kind of the opposite case, where as N gets bigger,

all of a sudden, F of N basically explodes

and gives a very high value.

All of a sudden your algorithm takes all this time to run

and needs to do all this work

in order to solve this particular problem.

So that's something we don't wanna see.

So growth functions basically give us a way

to tell how well this algorithm acts.

How much work is it gonna need to do?

How many operations is it gonna need to execute

in order to analyze and solve the problem that it was given.

When I say problem that was given,

really I'm saying is okay, we were given this input,

size in, our problem is to do something like sort it

and so what is it that it costs us,

in order to solve that problem of sorting that input array.

That's what I'm talking about.

Okay, so what we need to really do here,

to make our definition more precise,

is say what exactly it is F of N is computing.

So it's really not enough for it to say

the number of operations.

Because what does that even mean?

I mean, there are a thousand operations,

is an operation adding?

Is it subtracting?

Multiplying? Is it a bit shift?

Is it a logical operation?

Is it downloading a file?

It could be a thousand things.

And there's also the issue in there

of what level of abstraction are we talking about.

Are our operations something huge like downloading a file,

are they even larger?

Maybe they're like, sending a project to a development team.

We could have any sort of operation happening on

that right-hand side of a F of N thing.

So we need to pick what operation

is being counted, basically.

A lot of times, you won't see this, though.

If somebody ever asks you to do a big O on a function,

that question really even in itself,

doesn't really make sense.

To write a big O for function,

or to write a big F of N for function,

if you don't know what you're counting up,

right, because you could be counting anything.

Code isn't simple.

There's a thousand things happening in there,

how are you supposed to know what to actually measure?

What you measure has kind of, strong implications

for what that growth function will look like.

If I pick one thing, I get F of N equal one,

and the odds are then equal two,

another thing F of N equal N squared plus three.

And that's kind of an issue,

so I need to be very kind of specific

and know what exactly it is that I'm counting up.

What type of operation do I wanna look at.

I'll do some examples there,

to kind of illustrate the process of doing that.

In general, what you wanna do,

is you wanna pick an operation

that is very frequently occurring.

So we don't want you writing a growth function

for an operation that only happens once.

In that case, we basically don't have any knowledge

of how the input size relates to that growth function.

Because that growth function is measuring something

that only happens once, it's just very kind of,

well it's a constant.

It's just not interesting to us.

Second thing we look at is measuring something

that's very kind of heavy weight.

So, some operations are very, very quick,

for example, just an addition or a bit shift,

maybe it's not worth writing a big O for that,

or writing a growth function for it,

because it's something that happens very quickly.

But if we have something like,

maybe inside of a sorting function,

for example, maybe one of the things it does

is not just increment X or whatever,

but also calls a function to swap two elements in an array,

well that call to swap or exchange, or whatever you have,

that would be in and of itself something worth measuring.

Because that's a little bit more of a complex operation,

it's something that the algorithm is expressed in terms

of comparisons and exchanges and so it's worth it for us

to measure those exchanges and those comparisons.

Because that's kind of a basic operation

that takes a little bit of time in an algorithm.

And of course, we have the bonus there of,

oh those are things that happen reasonably frequently.

So that's what we wanna look at,

we wanna look for something like that.

Generally speaking, picking a specific thing to measure,

isn't gonna hold us back.

Sometimes people look at a huge function

and they get told to just analyze it

with respect to one line,

and they feel like, oh hey,

I'm gonna miss a bunch of things.

But that's not really true.

As long as you're picking what is basically,

the heavier duty work that needs to be done,

then your analysis is basically going to cover anything else

that happens in that function.

Even though there may be other things going on,

may be having other function calls in there,

other loops that are running.

If we have that, well then, as long as our analysis

is looking at the most heavy weight thing,

it's going to encompass, it's going to exceed anything else

that's happening in that function.

So it should be good for us to just stick with that

and not have to worry about everything else that's in there.

So as our first example, let's jump across

to the source code for binary search.

And let's just try and figure out,

what type of operation we might want to count up.

So overall, the process for doing our analysis here,

would be that we first start with some code,

then we pick an operation to count up,

then we write a growth function

that counts those operations based on the size as the input.

Then we have our big O and then from that big O,

maybe we can compute a tilde or a big O expression

from the growth function that we've recovered

from the bit of code.

That would be our general process.

So pick our operation, write a growth function,

then figure out big O or tilde.

So I'd just do the first part here,

and then later on we'll talk about how to do the rest of it.

So here we have binary search and the question is,

which line do we want to measure for our growth function?

Now let's go over these one by one.

So initially we have this sign over here,

int lo equals zero.

This line, just happens once.

So in that case, it's not really fair to use

that for our analysis, because it doesn't happen a lot.

We notice later on that there is a loop.

If there's a loop that's happening,

then that loop probably has some dependency

on how big the input is, right, how big is N?

But this first time I'm looking at it, it only happens once,

so there is no dependency there.

Well in that case, I probably don't want to measure it,

because it's not going to show me,

kind of the full behavior of this method.

I want to know how this method acts with respect

to how it's input size changes.

And this particular line, if I were to measure it,

I just don't have that.

This line will always happen, it'll happen exactly once.

So I'll skip it, not good.

This one over here, this line is also kind

of falling under the same idea,

in that it happens exactly once

and it's not impacted by the size of the input data.

So this is another one I would basically skip over.

One kind of quick note slash caveat here,

is that this little bit here

is actually important, pool dot length.

This part here is what's important to me.

This is basically just accessing a variable inside

of a object, arrays are objects in Java.

Now, if I just did the dot, I'm getting just a value.

That's fine, I'm not invoking a function.

If I had parentheses over here,

if I had length parenthesis parenthesis,

then I would be invoking a function.

And that would give me pause if I was doing analysis

of this program, because then I have to start to wonder,

what is the big O of that function?

Right, because maybe length, if it was a function,

what happens if that thing is big O of N cubed,

or F of N of N cubed?

All of a sudden, that kind of impacts my analysis

for this overall program here.

Right, so if I call functions,

I need to be a little bit careful.

So we just keep that in mind,

here's just a remember variable,

so we don't have to worry about it.

So we get to the next line, well,

so in here I'd probably don't wanna measure while.

While is just a statement

to show what's happening in the program.

what's happening over here though,

the operation, is this less than or equal to.

Where I check this lo and the hi variables.

This is actually going to be a good candidate for us,

because this while loop is basically going to run

until this condition is false,

but that's going to be for later on,

basically linked to the size of the input data.

More input data we have, the more time this loop will run.

So it would be a good idea potentially,

to look at that line there.

So I'm gonna put a check mark there

and over here I'll put in X's for these two lines

that didn't quite work out for us.

That one will be okay, we would measure our less than

or equal to, because it's going to basically depend

on how many times I need to compare something in my input.

Inside, I can see the actual math,

basically for adjusting hi and lo

and also a variable called mid.

Okay, so looking inside, what else do I have here?

My int and mid, this is another line

that probably would be okay for me to analyze

because nested right inside of the while loop,

every time the while loop runs, this line will run as well.

And the operation in there, I could measure the plus,

the minus, the divide, it's all the same thing.

These two lines are going to be the same.

They'll run effectively the same number of times.

The top one will run one more time because it needs to check

for the exit condition, but they're effectively the same.

I could pick each of those for analysis.

Looking down, the first if statement,

the operation there is a less than,

that'll actually also happen the same number

of times now that I'm thinking about it.

So let's add that in there, those are all the same.

So that'd be another kind of fair thing to analyze.

What that's checking basically is to see okay,

the target that I'm looking up is that gonna be less

than what I'm currently using as my mid point?

So I need to go and explore the left side,

versus I'd need to go explore the right side.

Remember this is binary search.

So that would be a fair thing to compare it as well.

Now we get down to this line here,

hi equal mid minus one.

This is a little bit problematic.

This line here, is happening under an if statement.

So there's some conditional logic

that must occur in order for us to run that line.

And the problem is, we don't really know,

will that line run or not?

Will hi equal mid run?

For the if statement, we know that's always gonna run,

right, cause it has to check that condition.

Regardless of whether it's true or false,

it still has to check it.

But inside of it, it has to be true in order for us

to actually run that inner line here.

It has to be true in order for us to do this stuff here.

So this has a dependency

and I would avoid analyzing that if I could.

And so the same thing actually applies

to the rest of the stuff in here.

So we're gonna have that else if, that else if code,

that's only running if that first if values to false.

So again, there's a dependency between whether this line

is run and what is the true value for the earlier thing.

So again, this is a line that I would not use.

The same thing will also apply to the last return

because again, it's like, what did that if of value do,

true or false, will it get here or not?

So those lines are all things that I would avoid.

So yeah, I can measure either my loop exit,

which is checking to see whether my bounds collide

or when I compute the mid point.

Either of those would be fair.

The last thing here, is this return false,

this return false is actually going to fall under

the category of these, in that they only happen once.

So if I get to the very end and I don't find the element,

I just run that statement once.

So actually there's two things

that are actually happening there.

One is that I don't wanna use it

because it only happens once.

Second thing is I don't wanna use it

because I don't know when it'll occur,

unless I know more about the data.

So there's an additional dependency there.

And we'll talk about, in a later video,

data dependencies in more detail.

So let's go over here and let's say,

let me fill this in.

So these, we kind of don't wanna use

because they take a constant amount of time,

these first two lines.

These second two were good,

because they have some core logic that happens,

and it happens regularly.

These five lines in here, we don't wanna use

because they all have an input dependence,

so I'll just call this an ID.

And then that last line is both constant time

and has instant input dependence.

So again, example of something we don't wanna use.

Okay so that's kind of a review of this particular function,

again, think in terms of, when I wanna want

to find a operation measure,

I wanna find something that's happens relatively frequently,

right, not constant time,

hopefully it's a relatively heavyweight operation.

Here we don't really have that notion

because everything's just kind of arithmetic,

so it's all kind of the same.

And then also maybe we want to be careful

that we pick things that aren't under logical expressions,

because then we'll have a hard time measuring them.

So keep those things in mind when you're analyzing code,

we'll do some more examples later.