DSA Big O
1.0.0
В этих тренировках вы будете практиковать определение большой сложности алгоритмов. Для каждой тренировки мы предоставим фрагмент кода с функцией, и вы выработаете большую сложность O, анализируя код без его запуска.
Определите большой O для следующего алгоритма: вы сидите в комнате с 15 людьми. Вы хотите найти приятеля для своей собаки, предпочтительно от той же породы. Таким образом, вы хотите знать, есть ли кто -нибудь из 15 человек, та же самая порода, что и ваша собака. Вы встаете и закричите, у которого здесь есть золотистый ретривер и хотел бы стать игрой для моего золотого. Кто -то кричит: «Я делаю, будь счастлив принести его»
Определите большой O для следующего алгоритма: вы сидите в комнате с 15 людьми. Вы хотите найти приятеля для вашей собаки, которая из той же породы. Таким образом, вы хотите знать, есть ли кто -нибудь из 15 человек, та же самая порода, что и ваша собака. Вы начинаете с первого человека и спрашиваете его, есть ли у него золотой ретривер. Он говорит «нет», затем вы спрашиваете следующего человека, а в следующем, а в следующем, пока не найдете кого -то, у кого есть золотой или никого, кто бы спросил.
Что такое большой O следующего алгоритма? Объясните свой ответ
if (value % 2 === 0) {
return true;
}
else {
return false;
}
}
Что такое большой O следующего алгоритма? Объясните свой ответ
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;
}
Что такое большой O следующего алгоритма? Объясните свой ответ
for (let i = 0; i < array.length; i++) {
array[i] *= 2;
}
return array;
}
Что такое большой O следующего алгоритма? Объясните свой ответ
for (let i = 0; i < array.length; i++) {
if (array[i] === item) {
return i;
}
}
}
Что такое большой O следующего алгоритма? Объясните свой ответ
for (let i = 0; i < arr.length; i++) {
for(let j = i + 1; j < arr.length; j++) {
console.log(arr[i] + ", " + arr[j] );
}
}
}
Что делает следующий алгоритм? Какова сложность его времени выполнения? Объясните свой ответ
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;
}
В этом примере мы возвращаемся к проблеме поиска с использованием более сложного подхода, чем в наивном поиске, выше. Предположим, что входной массив всегда отсортирован. Что такое большой O следующего алгоритма? Объясните свой ответ
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;
}
Что такое большой O следующего алгоритма? Объясните свой ответ
return arr[Math.floor(Math.random() * arr.length)];
}
Что делает следующий алгоритм? Что такое большой O следующего алгоритма? Объясните свой ответ
if (n < 2 || n % 1 !== 0) {
return false;
}
for (let i = 2; i < n; ++i) {
if (n % i === 0) return false;
}
return true;
}
Башня Ханоя - очень известная математическая головоломка (некоторые называют это игрой!). Вот как это происходит:
Есть три стержня и ряд дисков разных размеров, которые могут скользить на любой стержень. Головоломка начинается с дисков, аккуратно сложенных в порядке возрастания размера на одном стержне, наименьшем диском сверху (приготовление конической формы). Два других стержня пусты с самого начала.
Цель головоломки состоит в том, чтобы переместить всю стопку стержней в другой стержень (не может быть исходным стержнем, где он был сложен), где он будет сложен и в порядке возрастания. Это должно быть сделано, подчиняясь следующим правилам:
Ваша задача:
Решите упражнение JS -файл 12 итеративно вместо рекурсивно.
Возьмите решения из этого репо и определите временные сложности (Big O) каждого из них.
Возьмите свои решения из итерационных упражнений в Dlils в файле JS 12 и определите временные сложности (Big O) каждого из них.
