DSA Big O
1.0.0
Nesses exercícios, você praticará a determinação da grande complexidade dos algoritmos. Para cada exercício, forneceremos uma função de um trecho de código e você resolverá a grande complexidade O analisando o código sem executá -lo.
Determine o grande O para o algoritmo a seguir: você está sentado em uma sala com 15 pessoas. Você quer encontrar um companheiro de brincadeira para o seu cão, de preferência da mesma raça. Então você quer saber se alguém das 15 pessoas tem a mesma raça que seu cão. Você se levanta e grita, que aqui tem um Golden Retriever e gostaria de ser uma data de reprodução para o meu ouro. Alguém grita - "Eu faço, fique feliz em trazê -lo"
Determine o grande O para o algoritmo a seguir: você está sentado em uma sala com 15 pessoas. Você quer encontrar um companheiro de brincadeira para o seu cachorro que é da mesma raça. Então você quer saber se alguém das 15 pessoas tem a mesma raça que seu cão. Você começa com a primeira pessoa e pergunta se ele tem um Golden Retriever. Ele diz que não, então você pergunta à próxima pessoa, e a seguinte, e a seguinte até encontrar alguém que tenha um ouro ou não há mais ninguém para perguntar.
Qual é o grande O do algoritmo a seguir? Explique sua resposta
if (value % 2 === 0) {
return true;
}
else {
return false;
}
}
Qual é o grande O do algoritmo a seguir? Explique sua resposta
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;
}
Qual é o grande O do algoritmo a seguir? Explique sua resposta
for (let i = 0; i < array.length; i++) {
array[i] *= 2;
}
return array;
}
Qual é o grande O do algoritmo a seguir? Explique sua resposta
for (let i = 0; i < array.length; i++) {
if (array[i] === item) {
return i;
}
}
}
Qual é o grande O do algoritmo a seguir? Explique sua resposta
for (let i = 0; i < arr.length; i++) {
for(let j = i + 1; j < arr.length; j++) {
console.log(arr[i] + ", " + arr[j] );
}
}
}
O que o algoritmo a seguir faz? Qual é a sua complexidade de tempo de execução? Explique sua resposta
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;
}
Neste exemplo, retornamos ao problema de pesquisar usando uma abordagem mais sofisticada do que na pesquisa ingênua acima. Suponha que a matriz de entrada seja sempre classificada. Qual é o grande O do algoritmo a seguir? Explique sua resposta
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;
}
Qual é o grande O do algoritmo a seguir? Explique sua resposta
return arr[Math.floor(Math.random() * arr.length)];
}
O que o algoritmo a seguir faz? Qual é o grande O do algoritmo a seguir? Explique sua resposta
if (n < 2 || n % 1 !== 0) {
return false;
}
for (let i = 2; i < n; ++i) {
if (n % i === 0) return false;
}
return true;
}
A Torre de Hanói é um quebra -cabeça matemático muito famoso (alguns chamam de jogo!). É assim:
Existem três hastes e vários discos de tamanhos diferentes que podem deslizar para qualquer haste. O quebra -cabeça começa com os discos empilhados perfeitamente em ordem crescente de tamanho em uma haste, o menor disco na parte superior (fazendo uma forma cônica). As outras duas hastes estão vazias para começar.
O objetivo do quebra -cabeça é mover toda a pilha de hastes para outra haste (não pode ser a haste original onde foi empilhada antes), onde será empilhada na ordem ascendente também. Isso deve ser feito obedecendo às seguintes regras:
Sua tarefa:
Resolva o arquivo JS de broca 12 iterativamente, em vez de recursivamente.
Pegue as soluções deste repositório e identifique as complexidades do tempo (Big O) de cada uma delas.
Pegue suas soluções dos exercícios iterativos no arquivo JS 12 e identifique as complexidades do tempo (Big O) de cada uma delas.
