DSA Big O
1.0.0
Dans ces exercices, vous vous entraînerez à déterminer la grande complexité O des algorithmes. Pour chaque exercice, nous fournirons un extrait de code avec une fonction, et vous déterminerons la complexité Big O en analysant le code sans l'exécuter.
Déterminez le Big O pour l'algorithme suivant: Vous êtes assis dans une pièce avec 15 personnes. Vous voulez trouver un compagnon de jeu pour votre chien, de préférence de la même race. Vous voulez donc savoir si quelqu'un sur les 15 personnes a la même race que votre chien. Vous vous levez et hurlez, qui a ici un golden retriever et qui aime être un jeu de jeu pour mon Golden. Quelqu'un crie - "Je fais, soyez heureux de le ramener"
Déterminez le Big O pour l'algorithme suivant: Vous êtes assis dans une pièce avec 15 personnes. Vous voulez trouver un compagnon de jeu pour votre chien qui est de la même race. Vous voulez donc savoir si quelqu'un sur les 15 personnes a la même race que votre chien. Vous commencez par la première personne et lui demandez s'il a un golden retriever. Il dit non, alors vous demandez à la personne suivante, et la suivante, et la suivante jusqu'à ce que vous trouviez quelqu'un qui a un or ou il n'y a personne d'autre à demander.
Quel est le grand O de l'algorithme suivant? Expliquez votre réponse
if (value % 2 === 0) {
return true;
}
else {
return false;
}
}
Quel est le grand O de l'algorithme suivant? Expliquez votre réponse
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;
}
Quel est le grand O de l'algorithme suivant? Expliquez votre réponse
for (let i = 0; i < array.length; i++) {
array[i] *= 2;
}
return array;
}
Quel est le grand O de l'algorithme suivant? Expliquez votre réponse
for (let i = 0; i < array.length; i++) {
if (array[i] === item) {
return i;
}
}
}
Quel est le grand O de l'algorithme suivant? Expliquez votre réponse
for (let i = 0; i < arr.length; i++) {
for(let j = i + 1; j < arr.length; j++) {
console.log(arr[i] + ", " + arr[j] );
}
}
}
Que fait l'algorithme suivant? Quelle est sa complexité d'exécution? Expliquez votre réponse
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;
}
Dans cet exemple, nous revenons au problème de la recherche en utilisant une approche plus sophistiquée que dans la recherche naïve ci-dessus. Supposons que le tableau d'entrée est toujours trié. Quel est le grand O de l'algorithme suivant? Expliquez votre réponse
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;
}
Quel est le grand O de l'algorithme suivant? Expliquez votre réponse
return arr[Math.floor(Math.random() * arr.length)];
}
Que fait l'algorithme suivant? Quel est le grand O de l'algorithme suivant? Expliquez votre réponse
if (n < 2 || n % 1 !== 0) {
return false;
}
for (let i = 2; i < n; ++i) {
if (n % i === 0) return false;
}
return true;
}
La tour de Hanoi est un puzzle mathématique très célèbre (certains l'appellent le jeu!). C'est ainsi que ça se passe:
Il y a trois tiges et un certain nombre de disques de différentes tailles qui peuvent glisser sur n'importe quelle tige. Le puzzle commence par les disques soigneusement empilés dans un ordre ascendant de taille sur une tige, le plus petit disque en haut (faisant une forme conique). Les deux autres tiges sont vides pour commencer.
Le but du puzzle est de déplacer la pile entière de tiges vers une autre tige (ne peut pas être la tige d'origine où elle a été empilée auparavant) où elle sera également empilée dans l'ordre ascendant. Cela devrait être fait obéir aux règles suivantes:
Votre tâche:
Résolvez les exercices JS Fichier 12 itérativement au lieu de récursivement.
Prenez les solutions de ce dépôt et identifiez les complexités temporelles (Big O) de chacune d'elles.
Prenez vos solutions des exercices itératifs des exercices dans le fichier JS 12 et identifiez les complexités temporelles (Big O) de chacune d'elles.
