DSA Big O
1.0.0
En estos ejercicios, practicará determinar la gran complejidad de los algoritmos. Para cada taladro, proporcionaremos un fragmento de código con una función, y resolverá la gran complejidad de la O analizando el código sin ejecutarlo.
Determine la gran O para el siguiente algoritmo: está sentado en una habitación con 15 personas. Desea encontrar un compañero de juegos para su perro, preferiblemente de la misma raza. Entonces quieres saber si alguien de las 15 personas tiene la misma raza que tu perro. Te pones de pie y gritas, que aquí tiene un golden retriever y te gustaría ser una fecha de juego para mi oro. Alguien grita: "Yo sí, sé feliz de traerlo"
Determine la gran O para el siguiente algoritmo: está sentado en una habitación con 15 personas. Desea encontrar un compañero de juegos para su perro que sea de la misma raza. Entonces quieres saber si alguien de las 15 personas tiene la misma raza que tu perro. Empiezas con la primera persona y le preguntas si tiene un golden retriever. Él dice que no, luego le preguntas a la siguiente persona, y a la siguiente, y a la siguiente hasta que encuentres a alguien que tenga un oro o no hay nadie más a quien preguntar.
¿Cuál es la gran O del siguiente algoritmo? Explica tu respuesta
if (value % 2 === 0) {
return true;
}
else {
return false;
}
}
¿Cuál es la gran O del siguiente algoritmo? Explica tu respuesta
for (let i = 0; i < arr1.length; i++) {
const el1 = arr1[i];
for (let j = 0; j < arr2.length; j++) {
const el2 = arr2[j];
if (el1 === el2) return true;
}
}
return false;
}
¿Cuál es la gran O del siguiente algoritmo? Explica tu respuesta
for (let i = 0; i < array.length; i++) {
array[i] *= 2;
}
return array;
}
¿Cuál es la gran O del siguiente algoritmo? Explica tu respuesta
for (let i = 0; i < array.length; i++) {
if (array[i] === item) {
return i;
}
}
}
¿Cuál es la gran O del siguiente algoritmo? Explica tu respuesta
for (let i = 0; i < arr.length; i++) {
for(let j = i + 1; j < arr.length; j++) {
console.log(arr[i] + ", " + arr[j] );
}
}
}
¿Qué hace el siguiente algoritmo? ¿Cuál es su complejidad de tiempo de ejecución? Explica tu respuesta
let result = [];
for (let i = 1; i <= num; i++) {
if (i === 1) {
result.push(0);
}
else if (i === 2) {
result.push(1);
}
else {
result.push(result[i - 2] + result[i - 3]);
}
}
return result;
}
En este ejemplo, volvemos al problema de buscar el uso de un enfoque más sofisticado que en la búsqueda ingenua, arriba. Suponga que la matriz de entrada siempre está ordenada. ¿Cuál es la gran O del siguiente algoritmo? Explica tu respuesta
let minIndex = 0;
let maxIndex = array.length - 1;
let currentIndex;
let currentElement;
while (minIndex <= maxIndex) {
currentIndex = Math.floor((minIndex + maxIndex) / 2);
currentElement = array[currentIndex];
if (currentElement < item) {
minIndex = currentIndex + 1;
}
else if (currentElement > item) {
maxIndex = currentIndex - 1;
}
else {
return currentIndex;
}
}
return -1;
}
¿Cuál es la gran O del siguiente algoritmo? Explica tu respuesta
return arr[Math.floor(Math.random() * arr.length)];
}
¿Qué hace el siguiente algoritmo? ¿Cuál es la gran O del siguiente algoritmo? Explica tu respuesta
if (n < 2 || n % 1 !== 0) {
return false;
}
for (let i = 2; i < n; ++i) {
if (n % i === 0) return false;
}
return true;
}
La Torre de Hanoi es un rompecabezas matemático muy famoso (¡algunos lo llaman juego!). Así es como va:
Hay tres varillas y una serie de discos de diferentes tamaños que pueden deslizarse sobre cualquier barra. El rompecabezas comienza con los discos cuidadosamente apilados en orden ascendente de tamaño en una barra, el disco más pequeño en la parte superior (haciendo una forma cónica). Las otras dos barras están vacías para empezar.
El objetivo del rompecabezas es mover toda la pila de barras a otra barra (no puede ser la barra original donde fue apilada antes) donde también se apilará en el orden ascendente. Esto debe hacerse obedecer las siguientes reglas:
Tu tarea:
Resuelva el archivo JS de perforación 12 de forma iterativa en lugar de recursivamente.
Tome las soluciones de este repositorio e identifique las complejidades de tiempo (Big O) de cada uno de ellos.
Tome sus soluciones de los ejercicios de ejercicios iterativos en JS File 12 e identifique las complejidades de tiempo (Big O) de cada uno de ellos.
