[SER222] Characterizing Algorithms (3/5): Reviewing Terminology

Summary

En este video se revisan conceptos clave de cursos previos como SER200, CSE205 y MAT243, centrándose en el tamaño del problema (n) y cómo influye en el rendimiento de un algoritmo. Se explica la relación entre el tamaño de los datos de entrada y el tiempo de ejecución, utilizando ejemplos como listas, arrays y funciones recursivas. También se aborda el concepto de funciones de crecimiento, que cuentan operaciones en relación con el tamaño del problema, y la notación Big-O, que mide cómo crece el tiempo de ejecución a medida que aumenta el tamaño del problema.

Takeaways

• 📏 La variable (n) se utiliza para representar el tamaño del problema, como el tamaño de una lista o un arreglo que afecta el tiempo de ejecución de un algoritmo.
• 📊 Algunas entradas, como un número simple, no afectan el tiempo de ejecución del algoritmo, pero otras como colecciones (listas, arreglos) sí lo hacen.
• 🔄 En algoritmos recursivos, el valor de una entrada puede afectar la cantidad de llamadas recursivas, como en el caso de calcular un factorial recursivo.
• 📝 En algoritmos que procesan cadenas, como la inversión de una cadena, el tamaño de la entrada (longitud de la cadena) afecta el tiempo que tarda el algoritmo en ejecutarse.
• ⚖️ Las funciones de crecimiento, f(n), indican cómo crece el número de operaciones requeridas por un algoritmo a medida que aumenta el tamaño del problema.
• 📈 Un ejemplo de función de crecimiento es f(n)=1, lo que significa que el algoritmo siempre toma la misma cantidad de tiempo, independientemente del tamaño de la entrada.
• 🧮 La función f(n)=1+n representa un caso donde el algoritmo realiza una operación fija y luego realiza n operaciones adicionales, dependiendo del tamaño de la entrada.
• 💡 Las funciones de crecimiento son exactas, mientras que Big-O proporciona una estimación aproximada del comportamiento de un algoritmo a medida que crece el tamaño del problema.
• 🔠 La notación Big-O (como O(1), O(n), O(n²)) describe el comportamiento asintótico de un algoritmo, es decir, cómo se comporta cuando el tamaño del problema se vuelve grande.
• 📉 Big-O se utiliza para expresar el límite superior del tiempo de ejecución de un algoritmo, lo que significa que representa el peor caso posible en términos de operaciones necesarias.

Q & A

¿Qué significa el término 'tamaño del problema' (n) en el contexto de los algoritmos?

El 'tamaño del problema' (n) se refiere a la cantidad de datos que un algoritmo debe procesar, como el tamaño de una lista o un arreglo. El rendimiento del algoritmo depende del tamaño de la entrada.

¿Por qué un número como entrada no suele considerarse parte del tamaño del problema?

Un número como entrada no suele cambiar el tiempo de ejecución del algoritmo de manera significativa, a menos que esté involucrado en un proceso recursivo, como en el caso del factorial recursivo.

¿Cómo afecta el tamaño de una lista al rendimiento de un algoritmo?

Si la lista es más grande, el algoritmo tendrá que procesar más elementos, lo que aumenta el trabajo y el tiempo de ejecución. Por ejemplo, en un algoritmo de ordenación, el tiempo dependerá del número de elementos en la lista.

¿Qué es una función de crecimiento (growth function) en el análisis de algoritmos?

Una función de crecimiento es una fórmula que describe cómo crece el número de operaciones de un algoritmo en función del tamaño de la entrada. Se utiliza para calcular cuántas operaciones se necesitan para un tamaño de entrada determinado.

¿Cuál es la diferencia entre una función de crecimiento constante y una que varía con el tamaño del problema?

Una función de crecimiento constante, como f(n)=1, realiza la misma cantidad de operaciones sin importar el tamaño de la entrada. En cambio, una función como f(n)=1+n indica que a medida que el tamaño de la entrada crece, también aumenta el número de operaciones.

¿Cómo se relaciona una función de crecimiento con el tamaño de la entrada (n)?

Una función de crecimiento vincula el tamaño de la entrada (n) con la cantidad de trabajo que un algoritmo debe realizar. Por ejemplo, f(n)=n indica que por cada elemento adicional en la entrada, el número de operaciones aumenta en proporción directa.

¿Qué es la notación Big-O y cómo se utiliza?

La notación Big-O es una forma de describir el comportamiento asintótico de un algoritmo, indicando su rendimiento en función del tamaño de la entrada (n). Se utiliza para mostrar una cota superior del crecimiento de la función, ignorando constantes y términos pequeños.

¿Cuál es la diferencia entre una función de crecimiento exacta y la notación Big-O?

Una función de crecimiento exacta describe el número preciso de operaciones que un algoritmo ejecuta, mientras que la notación Big-O proporciona una aproximación que solo considera el comportamiento general cuando el tamaño de la entrada es grande.

¿Por qué la notación Big-O ignora constantes y términos menores?

La notación Big-O se enfoca en el comportamiento a largo plazo del algoritmo cuando el tamaño de la entrada (n) es grande. Las constantes y términos menores no tienen un impacto significativo en el crecimiento a gran escala, por lo que se omiten.

¿Cuándo es útil aplicar la notación Big-O en el análisis de algoritmos?

La notación Big-O es útil para analizar el rendimiento de un algoritmo cuando el tamaño de la entrada es grande. Ayuda a comparar la eficiencia de diferentes algoritmos en términos de su escalabilidad y rendimiento en situaciones reales.

Outlines

00:00

🧠 Revisión de Terminología: Tamaño del Problema (n)

Este párrafo aborda la importancia de entender el tamaño del problema (n) en el contexto de los algoritmos. Se explica que el tamaño del problema puede variar dependiendo de los tipos de entrada, como listas o arreglos, y cómo el tamaño afecta el tiempo de ejecución del algoritmo. Algunos parámetros, como números individuales, no afectan el tiempo de ejecución, mientras que colecciones como listas o arreglos sí lo hacen. Se mencionan ejemplos como el factorial recursivo y el proceso de ordenar arreglos, donde el tamaño de la entrada impacta directamente el comportamiento del algoritmo.

05:02

📈 Funciones de Crecimiento

En este párrafo, se explica el concepto de las funciones de crecimiento, que describen cómo crece una función en términos del número de operaciones que se ejecutan en un algoritmo dependiendo del tamaño de la entrada (n). Las funciones de crecimiento son exactas y permiten calcular cuántas operaciones requiere un algoritmo según el tamaño del problema. Ejemplos como f(n) = 1 y f(n) = 1 + n muestran cómo diferentes operaciones varían con el tamaño de la entrada. El crecimiento de una función depende de las operaciones y el número de elementos procesados.

Keywords

💡Tamaño del problema

El tamaño del problema (n) se refiere a la cantidad de datos que un algoritmo necesita procesar. Por ejemplo, en el caso de una lista o un arreglo, el tamaño del problema sería la cantidad de elementos que contiene. A medida que este tamaño aumenta, también lo hace el tiempo que toma el algoritmo para completarse, como en el caso del ordenamiento por inserción donde el tamaño del arreglo determina el número de operaciones necesarias.

💡Algoritmo

Un algoritmo es un conjunto de pasos o instrucciones que resuelven un problema específico. En el contexto del video, se mencionan diferentes tipos de algoritmos, como el de ordenamiento por inserción, que dependen del tamaño de la entrada (como una lista o un arreglo) para determinar el tiempo que tomarán en ejecutarse.

💡Recursividad

La recursividad es un concepto en el que una función se llama a sí misma para resolver subproblemas más pequeños. Un ejemplo mencionado en el video es la función factorial recursiva, donde el tamaño del número de entrada (como 'n' en el factorial) determina cuántas veces la función se llamará a sí misma, afectando el tiempo total de ejecución.

💡Función de crecimiento

Una función de crecimiento, f(n), describe cómo crece el número de operaciones necesarias para procesar un problema en función del tamaño del problema (n). Esta función mide cuántas operaciones se realizarán a medida que aumenta el tamaño de la entrada, por ejemplo, cuando se aumenta el tamaño de un arreglo en un algoritmo de ordenamiento.

💡Operación

Una operación es una acción ejecutada por un algoritmo, como una comparación o un intercambio de elementos en un arreglo. En el video, se menciona que las funciones de crecimiento cuentan cuántas operaciones se requieren para ejecutar un algoritmo, y cómo varía la cantidad de estas según el tamaño de la entrada.

💡Big-Oh

El Big-Oh (O grande) es una notación que se utiliza para describir el comportamiento asintótico de un algoritmo, es decir, cómo crece su tiempo de ejecución o espacio necesario en función del tamaño de la entrada (n). Por ejemplo, O(n) significa que el número de operaciones crece linealmente con el tamaño de la entrada. Se usa para simplificar la descripción del rendimiento de los algoritmos, omitiendo detalles menores como constantes.

💡Complejidad temporal

La complejidad temporal mide cuánto tiempo tarda un algoritmo en ejecutarse en función del tamaño de la entrada. Por ejemplo, un algoritmo con una complejidad de O(n²) tomará más tiempo en completarse si el tamaño de la entrada aumenta significativamente, en comparación con un algoritmo con O(n).

💡Entrada del algoritmo

La entrada de un algoritmo son los datos que el algoritmo necesita procesar, como una lista, un número o una cadena de caracteres. El video explica que el tipo y tamaño de la entrada afectan directamente la cantidad de trabajo que el algoritmo debe realizar. Por ejemplo, ordenar una lista de 10 elementos tomará menos tiempo que ordenar una lista de 100 elementos.

💡Factorial

El factorial es un ejemplo de función matemática que puede implementarse de manera recursiva. En el video, se menciona cómo el número de llamadas recursivas en una función factorial depende del valor de la entrada, lo que afecta el tiempo que toma completarse. A mayor número, más llamadas recursivas y mayor el tiempo de ejecución.

💡Asintótico

El comportamiento asintótico de un algoritmo describe cómo se comporta su rendimiento cuando el tamaño de la entrada es muy grande. En el video, se hace referencia a esto en el contexto de la notación Big-Oh, que se usa para representar el rendimiento de un algoritmo cuando el tamaño de la entrada crece indefinidamente.

Highlights

Review of terminology related to algorithm problem size and growth functions.

The importance of problem size (n) and its effect on algorithm performance, particularly with arrays and lists.

Distinction between inputs that impact algorithm runtime, such as arrays or lists, versus inputs that don't, like constants.

Recursive functions' dependence on the size of the integer input, with recursive factorial as an example.

Definition of growth functions (f(n)) to show how an algorithm's number of operations grows with the problem size.

The relationship between the input size of an algorithm and the number of operations required, exemplified with an input array of size 10.

Explanation of different types of growth functions, such as f(n) = 1 (constant) and f(n) = 1 + n (linear).

Understanding how growth functions vary based on the size of the input, particularly in list traversal or element processing.

Emphasis on growth functions being exact in representing the number of operations required by an algorithm.

Introduction to Big-O notation (O(1), O(n), O(n^2)) to express the upper bound or long-term behavior of an algorithm's runtime.

Big-O notation's purpose in simplifying the expression of algorithm efficiency, removing constants and lower-order terms.

Example of 2n + 15 being O(n), as constants and coefficients are considered insignificant as n grows.

Big-O notation primarily represents the worst-case scenario or upper bound of an algorithm's performance.

Focus on Big-O notation for large input sizes, as small inputs can cause irregularities in performance comparisons.

General guidance that Big-O notation is used to represent long-term behavior, when input sizes become 'sufficiently large.'

Transcripts

- In this video, I wanna spend a few minutes

to review some terminology from previous classes.

So this should all be material that you see

either in SER200 or CSE205, or MAT243.

Hopefully, none of this is new,

I'm not going to spend all that much time on it.

Really, all I want to do is just make sure

we're kind of on the same page.

So the first thing I wanna talk about here

is what we call N, or the problem size.

So a lot of times where we have an algorithm,

and this algorithm has a bunch of inputs,

and those inputs maybe have different types, right,

maybe I given it a number, maybe I give it a list.

Well, the list in particular is a little bit interesting

because basically, that algorithm, right,

will take a different amount of time to run,

whether that list has one thing in it,

or ten things in it, or twenty things in it.

There's a dependency between an algorithm and it's input.

And so that list that is being processed, right,

we have to care about how big it is, right?

And so what we'll say is it is size (n),

and in fact, it defines the problem size.

I'm just using this here as an example,

it also could be something like an array.

Right, so if you think back to insertion sort,

insertion sort takes an array to be sorted.

The problem size links that array.

And so we would say that the length of that array

is (n).

Now typically an algorithm will have multiple inputs

some of those will just be something like a number.

A number doesn't really count as problem size

the reason for that is that adjusting that number

typically doesn't change how long

that algorithm takes to run.

So maybe that number has a cutoff you know,

throw away all the values less than (k) right,

in this input list.

Well what we choose for (k)

really doesn't matter all that much, right?

It's the cut off that will always be applied the same way.

Versus if I have a list going in, right?

And it has different elements in there.

Well, the algorithm has to do more work

if there's more elements, right.

And maybe through some like sorting right,

in which case basically your problem

is right, that you have to move around more things.

Right, that's clearly more work

versus just you know changing what is

the cut off or the threshold that's being enforced

and something else.

So some inputs really matter,

some don't.

Some basically you treat as constants because

they don't effect the running time of the program.

But when you have a collection, right

an array or a list.

Then we care about and typically we say is

that defines the problem size, right, (n).

Sometimes if you take in more than one collection,

you'll say maybe you have (m) and (n), right,

it depends on the size of two things.

So (n) can vary in a lot of different ways.

We're just talking about collection size here,

so maybe that's something like sorting.

Another thing we could have if maybe we were talking

about recursive function is maybe we do have an integer,

but that integer actually doesn't pack how long

the algorithm takes to run.

So let's say something like recursive factorial

and recursive factorial,

the value of that parameter is going to control

how many recursive calls you make.

So the larger that number,

the more calls you will make.

Right, lower number, fewer calls.

So that actually does change the algorithm's performance.

It's not just, you know, inside of an if statement

that does that cuts out all of these values less than (k)

Right, it's actually having some impact on

the number of times that function loops,

the number of times that function calls itself.

Now, in that case, that algorithm actually depends

on that input.

So in that case, it would be fair to say,

that that's part of our problem size, right.

So the factorial number, you know may be the factorial

of (i),

that also doubles as a problem size,

and then maybe we just call it (n).

Because that's how big our problem is.

All right, we are trying to compute with the

factorial of ten.

And it's going to take me basically ten step to get there.

So that's another idea of size.

The last example here, is in terms of strings.

Maybe I have an algorithm that reverses a string,

well in that case then,

I am going to need to through

and touch every character inside there

and change it's position.

Well, again, right that algorithm is going to

take a different amount of time to run,

whether it has ten characters or 100 characters.

There some sort of dependence between

the length of that input and how long the algorithm takes.

So, again now, that would kind of fall under

things we need to care about.

You know, how big they are, right?

Because it defines our problem size.

So in general, right, an algorithm

is going to be defined under some sort of parameters,

and then some of those parameters are going to have

some sort of sizes associated with them, right.

And those sizes are what we are going to have to

keep track of if we are trying to figure out

how this thing acts.

Because how long it takes to run will vary

with the sizes of the parameters

that are going into it.

All right, so that is our idea of (n).

Our problem size, right.

How big is something?

How much work do I have to do?

The next thing that I want to talk about

is growth functions.

So, growth functions have kind of a specific meaning.

So, growth functions are really just some f(n).

Right, so they're some function.

The significance though,

and why we call them growth functions,

is because growth functions are showing

how a function grows.

Grows in terms of operations,

so the typical f(n) is counting up a number of operations

and really though we should be more specific there.

We want to count up some specific action.

Right, some specific thing the algorithm is doing.

For now, I'll just say operation.

So you can assume that maybe it's executing

a line of code.

Right, the number of things that have happened.

You know, the number of instructions

that need to be executed on the CPU.

Something like that.

Well a growth function is basically a normal function.

That's meant to count up how many operations will

be required for a given input size.

Right, so I can say

"Hey, I have an input array of size ten."

And then my growth function will compute for me,

oh that means it will take a hundred operations

for you to process that.

That is the basic idea of a growth function.

It's giving us a way to calculate a number of

operations from the problem size.

We're linking (n) to amount of work that needs to be done.

So for a lot of analysis,

usually what we want to do is,

you want to find out what is the growth function.

And that's something you hopefully have done

in a previous course,

is actually write a growth function from a bit of code.

We'll be doing it again here in this course,

but hopefully you have done it before as well.

I have some quick examples down there,

f(n)=1 is an example of a potential growth function.

What that is, is saying,

"Okay, I have a growth function that no matter

input I give it, it always takes one operation to complete."

All right, so maybe it's something that doesn't do very much

it just does a fixed amount of work,

maybe it adds a number,

right, maybe it just increases something,

and that's really just one line of code, right.

Or returns something that's just one line of code.

Very simple.

Versus something like f(n)=1+(n)

what that's saying is,

"Oh you're doing a little bit of work, right,

you're doing one operation,

plus (n) other things."

So maybe that's where you're going through a list,

and maybe you're increasing everything in it.

Right, you need to go in and touch

every element in there.

In that case, that (n) parameter,

the problem size,

is based on the size of the input collection.

The number of elements in that list.

And so as that list gets bigger,

the growth functions basically going to grow.

Every time you add one to the input size,

it's going to take one extra operation to process it.

So in that case, basically,

our growth function varies as our input size does,

where in the first example it does not vary, right.

It's a constant amount of operations are executed

based off of any input.

And really there in f(n)=1,

it's a little bit awkward because

that (n) is still there,

so we're still saying that the problem size can vary,

but somehow there is just no link, right,

between that and the number of operations it takes

to run.

So it's a little bit awkward,

but we do see that in some cases.

As a final note here,

one thing that is going to be different

about growth functions for us in this course,

is that growth functions are meant to be exact.

So, they should exactly tell us how many operations

are going to be required,

or maybe how much time will this algorithm take.

Right, so they should be exact solutions,

they are not intended to be approximate.

For approximate, we have something else.

We'll have different names of things.

Growth function is supposed to be exact.

The last terminology that I want to talk about

is Big-Oh.

So, big-oh means something like,

0(1) or 0(n) or 0(n²), right, or 0(n³) or 0(n)² or whatever.

You should have seen this before in a previous class.

These are all big-oh expressions,

maybe I would call them big-oh terms.

They're using what is called big-oh notation.

What big-oh notation is,

is a way to write an exact quality.

Well, an inexact quantity.

So, 0(1) is basically saying,

"Oh, it's just some number."

0(n) is saying,

"Oh, it's some number times (n)."

So, I'm not giving a specific number,

I'm not saying it's 2(n) or 4(n) or 5(n),

I'm just saying it's something that is a multiple of (n).

Right, grows like (n) with a constant in front.

And so, basically, big-oh is used as a summary.

Right, so take a look down there at the expression I have,

so I have the expression 2(n)+15=0(n),

what that is saying is that expression 2(n)+15

is big-oh of (n).

Right, so 2(n)+15 is 0(n).

So basically we are saying,

"Oh hey, this function, right, as I change the value of (n),

it's going to basically act like a linear function."

It's going to act like just (n).

Yeah, in the full function,

that plus 15 is in there as well,

but it really doesn't matter.

It's a constant, its going to be small.

If (n) becomes really large,

the impact of that 15 doesn't really matter.

And then, just for convenience,

big-oh is basically hiding an invisible coefficient

in front of that letter.

In front of that variable.

So that 2 kind of goes away as well.

Now if we had something else like for example,

say we had 10(N)+2,

that as well would be 0(n),

because again it's just some expression that varies

with some multiple of (n).

It says that expression is inside that 0 notaton.

Overall, right, big-oh is giving us this way

to basically write a quantity that varies a little bit

and somehow there is also this typical notion in there

that it is going to be larger than something.

So, that big-oh typically is representing what we call

an upper bound.

I'll talk about that a lot more in a minute.

That's going to be some value,

that always stays above something else.

So 0(n) should always stay above,

right picture you have a graph in your head,

it'll always stay above that 2n+15.

So that's what we would typically use big-oh for

as it represents upper bound on something.

It shadows something.

A final note there,

is that we typically use big-oh in terms of

long term behavioral function.

So once, you know our input size gets really big.

For various reasons,

and we will talk about them,

it's hard basically to compare functions,

or to talk about functions,

when their input size basically is really small.

So it's like zero, one, two, three, four,

somehow things are going to be a little bit noisy.

And you can look at that graph on the right,

maybe to get a some conceptual idea there.

So big-oh somehow is used generally when we

expect (n) to be "sufficiently large"

and I using air quotes there because

sufficiently large isn't really defined,

it's just what people say.