Complejidad y sesión de problemas
La complejidad en ciencias de la computación es una medida de estimación del uso de recursos. Supongamos que ejecutamos un for que hace n iteraciones, esto podría declarar variables, modificarlas, asignarlas, etc. Pero en esencia, la ejecución del for hace que la computadora haga un estimado de n cálculos, de forma simple lo denotamos como O(n).
for (int i = 1; i <= n; ++i) {
/**
* este for puede hacer más cálculos
* en su cuerpo, pero por ahora preocupemonos
* sobre los recursos que se usan solo para
* ejecutar el for.
*/
process(i);
}
Muchos piensan que la complejidad solo tiene que ver con el tiempo de ejecución, pero la complejidad sirve para medir todo tipo de recursos, en ese sentido podemos hablar de complejidad de memoria. La complejidad de memoria es algo más difícil de medir que la complejidad de las operaciones, y se define como la mayor cantidad de memoria que usa en total un programa en un determinado instante.
/**
* Este algoritmo halla el menor numero de
* n elementos, pero no es la mejor forma de hacerlo.
*/
vector<int> arr;
for (int i = 1; i <= n; ++i) {
arr.push_back(a[i]); //<-- agrego un elemento a un array
sort(begin(arr), end(arr)); //<-- aca ordeno los elementos
if (arr.size() > 1) {
arr.pop_back(); //<-- si hay al menos 2 elementos, elimino el mayor .
}
}
El algoritmo anterior, agrega al array arr n elementos, pero sin embargo a lo mucho hay 2 elementos en este array, eso lo podemos entender que a lo más el algoritmo usa dos espacios de memoria y por tanto diremos que el algoritmo usa O(2) de memoria.
Propiedades de la complejidad
No necesitamos un conocimiento avanzado de complejidad algorítmica, solo nos basta algunas nociones para trabajar, por el momento, con problemas.
Una propiedad útil de la complejidad algorítmica es la absorción. dada una constante c y una función f, O(cf(n)) es asintóticamente igual a O(f(n)). De forma similar funciones con mayor crecimiento absorben a las funciones con menor crecimiento, por ejemplo: O(n^2 + n) = O(n^2).
Ejemplos de código.
for (int i = 1; i <= n; ++i) {
cout << "hello" << endl;
}
-
que complejidad tiene el anterior código.
-
cuantas veces se imprime “hello”.
for (int i = 1; i <= n; ++i) {
if (n % i == 0) {
cout << "hello" << endl;
}
}
-
que complejidad tiene el anterior código.
-
cuantas veces se imprime “hello”.
for (int i = 1; i*i <= n; ++i) {
if (n % i == 0) {
cout << "hello" << endl;
}
}
-
que complejidad tiene el anterior código.
-
cuantas veces se imprime “hello”.
for (int i = 1; i*i <= n; ++i) {
int a;
}
- que complejidad tiene el anterior código.
for (int i = 1; i*i <= n; i += i) {
int a;
}
- que complejidad tiene el anterior código.