DSA Big O
1.0.0
Dalam latihan ini, Anda akan berlatih menentukan kompleksitas besar algoritma. Untuk setiap bor, kami akan memberikan cuplikan kode fungsi, dan Anda akan mengerjakan kompleksitas O besar dengan menganalisis kode tanpa menjalankannya.
Tentukan O besar untuk algoritma berikut: Anda duduk di kamar dengan 15 orang. Anda ingin menemukan teman bermain untuk anjing Anda, lebih disukai dari jenis yang sama. Jadi, Anda ingin tahu apakah ada orang dari 15 orang yang memiliki jenis yang sama dengan anjing Anda. Anda berdiri dan berteriak, yang di sini memiliki golden retriever dan ingin menjadi papan bermain untuk emas saya. Seseorang berteriak - "Ya, dengan senang hati membawanya"
Tentukan O besar untuk algoritma berikut: Anda duduk di kamar dengan 15 orang. Anda ingin menemukan teman bermain untuk anjing Anda yang memiliki jenis yang sama. Jadi, Anda ingin tahu apakah ada orang dari 15 orang yang memiliki jenis yang sama dengan anjing Anda. Anda mulai dengan orang pertama dan bertanya apakah dia memiliki golden retriever. Dia bilang tidak, lalu Anda bertanya kepada orang berikutnya, dan berikutnya, dan berikutnya sampai Anda menemukan seseorang yang memiliki emas atau tidak ada orang lain untuk bertanya.
Apa o besar dari algoritma berikut? Jelaskan jawaban Anda
if (value % 2 === 0) {
return true;
}
else {
return false;
}
}
Apa o besar dari algoritma berikut? Jelaskan jawaban Anda
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;
}
Apa o besar dari algoritma berikut? Jelaskan jawaban Anda
for (let i = 0; i < array.length; i++) {
array[i] *= 2;
}
return array;
}
Apa o besar dari algoritma berikut? Jelaskan jawaban Anda
for (let i = 0; i < array.length; i++) {
if (array[i] === item) {
return i;
}
}
}
Apa o besar dari algoritma berikut? Jelaskan jawaban Anda
for (let i = 0; i < arr.length; i++) {
for(let j = i + 1; j < arr.length; j++) {
console.log(arr[i] + ", " + arr[j] );
}
}
}
Apa yang dilakukan algoritma berikut? Apa kompleksitas runtime -nya? Jelaskan jawaban Anda
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;
}
Dalam contoh ini, kami kembali ke masalah pencarian menggunakan pendekatan yang lebih canggih daripada dalam pencarian naif, di atas. Asumsikan bahwa array input selalu diurutkan. Apa o besar dari algoritma berikut? Jelaskan jawaban Anda
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;
}
Apa o besar dari algoritma berikut? Jelaskan jawaban Anda
return arr[Math.floor(Math.random() * arr.length)];
}
Apa yang dilakukan algoritma berikut? Apa o besar dari algoritma berikut? Jelaskan jawaban Anda
if (n < 2 || n % 1 !== 0) {
return false;
}
for (let i = 2; i < n; ++i) {
if (n % i === 0) return false;
}
return true;
}
Tower of Hanoi adalah teka -teki matematika yang sangat terkenal (beberapa menyebutnya game!). Beginilah caranya:
Ada tiga batang dan sejumlah disk dengan ukuran berbeda yang dapat meluncur ke batang apa pun. Teka -teki dimulai dengan disk yang ditumpuk rapi dalam urutan menaikkan ukuran pada satu batang, disk terkecil di bagian atas (membuat bentuk kerucut). Dua batang lainnya kosong untuk memulai.
Tujuan dari teka -teki ini adalah untuk memindahkan seluruh tumpukan batang ke batang lain (tidak bisa menjadi batang asli di mana ia ditumpuk sebelumnya) di mana ia akan ditumpuk dalam urutan naik juga. Ini harus dilakukan mematuhi aturan berikut:
Tugas Anda:
Selesaikan file bor JS 12 secara iteratif alih -alih secara rekursif.
Ambil solusi dari repo ini dan identifikasi kompleksitas waktu (o besar) masing -masing.
Ambil solusi Anda dari latihan latihan berulang dalam file JS 12 dan identifikasi kompleksitas waktu (besar O) masing -masing.
