DSA Big O
1.0.0
In diesen Übungen üben Sie die Bestimmung der großen O -Komplexität von Algorithmen. Für jeden Drill geben wir ein Code -Snippet mit einer Funktion an und werden die große O -Komplexität erarbeiten, indem Sie den Code analysieren, ohne ihn auszuführen.
Bestimmen Sie das große O für den folgenden Algorithmus: Sie sitzen in einem Raum mit 15 Personen. Sie möchten einen Spielkameraden für Ihren Hund finden, vorzugsweise dieselbe Rasse. Sie möchten also wissen, ob jemand von den 15 Personen die gleiche Rasse wie Ihr Hund hat. Sie stehen auf und schreien, der hier einen goldenen Retriever hat und möchte ein Spiel für meinen Goldenen sein. Jemand schreit - "Ich tue es, freut sich, ihn zu übernehmen"
Bestimmen Sie das große O für den folgenden Algorithmus: Sie sitzen in einem Raum mit 15 Personen. Sie möchten einen Spielkameraden für Ihren Hund finden, der die gleiche Rasse hat. Sie möchten also wissen, ob jemand von den 15 Personen die gleiche Rasse wie Ihr Hund hat. Sie beginnen mit der ersten Person und fragen ihn, ob er einen goldenen Retriever hat. Er sagt nein, dann fragst du die nächste Person und die nächste und die nächste, bis du jemanden findet, der einen Goldenen oder es gibt niemanden, der sie fragen kann.
Was ist das große O des folgenden Algorithmus? Erklären Sie Ihre Antwort
if (value % 2 === 0) {
return true;
}
else {
return false;
}
}
Was ist das große O des folgenden Algorithmus? Erklären Sie Ihre Antwort
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;
}
Was ist das große O des folgenden Algorithmus? Erklären Sie Ihre Antwort
for (let i = 0; i < array.length; i++) {
array[i] *= 2;
}
return array;
}
Was ist das große O des folgenden Algorithmus? Erklären Sie Ihre Antwort
for (let i = 0; i < array.length; i++) {
if (array[i] === item) {
return i;
}
}
}
Was ist das große O des folgenden Algorithmus? Erklären Sie Ihre Antwort
for (let i = 0; i < arr.length; i++) {
for(let j = i + 1; j < arr.length; j++) {
console.log(arr[i] + ", " + arr[j] );
}
}
}
Was macht der folgende Algorithmus? Was ist seine Laufzeitkomplexität? Erklären Sie Ihre Antwort
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;
}
In diesem Beispiel kehren wir mit einem ausgefeilteren Ansatz zu dem Problem der Suche zurück als bei naiver Suche oben. Angenommen, das Eingangsarray ist immer sortiert. Was ist das große O des folgenden Algorithmus? Erklären Sie Ihre Antwort
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;
}
Was ist das große O des folgenden Algorithmus? Erklären Sie Ihre Antwort
return arr[Math.floor(Math.random() * arr.length)];
}
Was macht der folgende Algorithmus? Was ist das große O des folgenden Algorithmus? Erklären Sie Ihre Antwort
if (n < 2 || n % 1 !== 0) {
return false;
}
for (let i = 2; i < n; ++i) {
if (n % i === 0) return false;
}
return true;
}
Der Turm von Hanoi ist ein sehr berühmtes mathematisches Puzzle (einige nennen es Spiel!). So geht es:
Es gibt drei Stangen und eine Reihe von Scheiben unterschiedlicher Größen, die auf jede Stange gleiten können. Das Puzzle beginnt mit den Scheiben, die ordentlich in aufsteigender Größenreihenfolge auf einer Stange gestapelt sind, der kleinsten Scheibe oben (eine konische Form hergestellt). Die anderen beiden Stangen sind anfangs leer.
Das Ziel des Puzzles ist es, den gesamten Stapel Stäbchen zu einer anderen Stange zu bewegen (kann nicht die ursprüngliche Stange sein, auf der es vorher gestapelt wurde), wo es auch in der aufsteigenden Reihenfolge gestapelt wird. Dies sollte geschehen, um den folgenden Regeln zu befolgen:
Ihre Aufgabe:
Lösen Sie die Bohrer JS -Datei 12 iterativ anstatt rekursiv.
Nehmen Sie die Lösungen aus diesem Repo und identifizieren Sie die zeitliche Komplexität (Big O) von jedem von ihnen.
Nehmen Sie Ihre Lösungen aus den iterativen Übungsübungen in der JS -Datei 12 und identifizieren Sie die zeitliche Komplexität (Big O) von jedem von ihnen.
