Einführung in DSA und Big-O-Notation

Hinweise zum Master-DSA:

Master DSA soll „Anspruch“ auf hochbezahlte Gehälter haben, die S/W-Mitarbeitern angeboten werden.
DSA ist der Hauptteil des Software Engineering.
Stellen Sie vor dem Schreiben von Code sicher, dass Sie das Gesamtbild verstehen, und gehen Sie dann ins Detail.
Es geht darum, die Konzepte visuell zu verstehen und diese Konzepte dann über ein beliebiges L/G in Code zu übersetzen, da DSA sprachunabhängig ist.
Jedes kommende Konzept ist irgendwie mit früheren Konzepten verknüpft. Überspringen Sie daher keine Themen und kommen Sie nicht weiter, es sei denn, Sie haben das Konzept gründlich gemeistert, indem Sie es geübt haben.
Wenn wir Konzepte visuell lernen, erlangen wir ein tieferes Verständnis des Materials, was uns wiederum hilft, das Wissen länger zu behalten.
Wenn Sie diese Ratschläge befolgen, haben Sie nichts zu verlieren.

Linear DS:
Arrays
LinkedList(LL) & Doubly LL (DLL)
Stack
Queue & Circular Queue

Non-linear DS:
Trees
Graphs

Big-O-Notation

Es ist wichtig, diese Notation für den Leistungsvergleich von Algen zu verstehen.
Es ist eine mathematische Methode zum Vergleich der Effizienz von Algen.

Zeitkomplexität

Je schneller der Code ausgeführt wird, desto niedriger wird er sein
V. ist für die meisten Interviews verantwortlich.

Weltraumkomplexität

Wird im Vergleich zur zeitlichen Komplexität aufgrund der geringen Speicherkosten selten berücksichtigt.
Muss verstanden werden, da ein Interviewer Sie möglicherweise auch danach fragt.

Drei griechische Buchstaben:

1. Omega
2. Theta
3. Omicron i.e. Big-O [am häufigsten gesehen]

Fälle für algo

1. Bester Fall [dargestellt durch Omega]
2. Durchschn. Fall [dargestellt mit Theta]
3. Worst Case [dargestellt mit Omicron]

Technisch gesehen gibt es keinen besten Fall von Big-O. Sie werden jeweils mit Omega und Theta bezeichnet.
Wir messen immer den schlimmsten Fall.

## O(n): Efficient Code
Proportional
Its simplified by dropping the constant values.
An operation happens 'n' times, where n is passed as an argument as shown below.
Always going to be a straight line having slope 1, as no of operations is proportional to n.
X axis - value of n.
Y axis - no of operations 

// O(n)
function printItems(n){
  for(let i=1; i<=n; i++){
    console.log(i);
  }
}
printItems(9);

// O(n) + O(n) i.e O(2n) operations. As we drop constants, it eventually becomes O(n)
function printItems(n){
  for(let i=0; i<n; i++){
    console.log(i);
  }
  for(let j=0; j<n; j++){
    console.log(j);
  }
}
printItems(10);

## O(n^2):
Nested loops.
No of items which are output in this case are n*n for a 'n' input.
function printItems(n){
  for(let i=0; i<n; i++){
    console.log('\n');
    for(let j=0; j<n; j++){
      console.log(i, j);
    }
  }
}
printItems(4);

## O(n^3):
No of items which are output in this case are n*n*n for a 'n' input.
// O(n*n*n)
function printItems(n){
  for(let i=0; i<n; i++){
    console.log(`Outer Iteration ${i}`);
    for(let j=0; j<n; j++){
      console.log(`  Mid Iteration ${j}`);
      for(let k=0; k<n; k++){
        //console.log("Inner");
        console.log(`    Inner Iteration ${i} ${j} ${k}`);
      }
    }
  }
}
printItems(3);


## Comparison of Time Complexity:
O(n) > O(n*n)


## Drop non-dominants:
function xxx(){
  // O(n*n)
  Nested for loop

  // O(n)
  Single for loop
}
Complexity for the below code will O(n*n) + O(n) 
By dropping non-dominants, it will become O(n*n) 
As O(n) will be negligible as the n value grows. O(n*n) is dominant term, O(n) is non-dominnat term here.

## O(1):
Referred as Constant time i.e No of operations do not change as 'n' changes.
Single operation irrespective of no of operands.
MOST EFFICIENT. Nothing is more efficient than this. 
Its a flat line overlapping x-axis on graph.


// O(1)
function printItems(n){
  return n+n+n+n;
}
printItems(3);


## Comparison of Time Complexity:
O(1) > O(n) > O(n*n)

## O(log n)
Divide and conquer technique.
Partitioning into halves until goal is achieved.

log(base2) of 8 = 3 i.e we are basically saying 2 to what power is 8. That power denotes the no of operations to get to the result.

Also, to put it in another way we can say how many times we need to divide 8 into halves(this makes base 2 for logarithmic operation) to get to the single resulting target item which is 3.

Ex. Amazing application is say for a 1,000,000,000 array size, how many times we need to cut to get to the target item.
log(base 2) 1,000,000,000 = 31 times
i.e 2^31 will make us reach the target item.

Hence, if we do the search in linear fashion then we need to scan for billion items in the array.
But if we use divide & conquer approach, we can find it in just 31 steps.
This is the immense power of O(log n)

## Comparison of Time Complexity:
O(1) > O(log n) > O(n) > O(n*n)
Best is O(1) or O(log n)
Acceptable is O(n)

O(n log n) : 
Used in some sorting Algos.
Most efficient sorting algo we can make unless we are sorting only nums.

Tricky Interview Ques: Different Terms for Inputs.
function printItems(a,b){
  // O(a)
  for(let i=0; i<a; i++){
    console.log(i);
  }
  // O(b)
  for(let j=0; j<b; j++){
    console.log(j);
  }
}
printItems(3,5);

O(a) + O(b) we can't have both variables equal to 'n'. Suppose a is 1 and b is 1bn.
Then both will be very different. Hence, it will eventually be O(a + b) is what can call it.
Similarly if these were nested for loops, then it will become O(a * b)

## Arrays
No reindexing is required in arrays for push-pop operations. Hence both are O(1).
Adding-Removing from end in array is O(1)

Reindexing is required in arrays for shift-unshift operations. Hence, both are O(n) operations, where n is no of items in the array.
Adding-Removing from front in array is O(n)

Inserting anywhere in array except start and end positions:
myArr.splice(indexForOperation, itemsToBeRemoved, ContentTobeInsterted)
Remaining array after the items has to be reindexed.
Hence, it will be O(n) and not O(0.5 n) as Big-O always meassures worst case, and not avg case. 0.5 is constant, hence its droppped.
Same is applicable for removing an item from an array also as the items after it has to be reindexed.


Finding an item in an array:
if its by value: O(n)
if its by index: O(1)

Select a DS based on the use-case.
For index based, array will be a great choice.
If a lot of insertion-deletion is perform in the begin, then use some other DS as reindexing will make it slow.

Vergleich der Zeitkomplexität für n=100:

O(1) = 1
O(log 100) = 7
O(100) = 100
O(n^2) = 10.000

Vergleich der Zeitkomplexität für n=1000:

O(1) = 1
O(log 1000) = ~10
O(1000) = 1000
O(1000*1000) = 1.000.000

Wir werden uns hauptsächlich auf diese 4 konzentrieren:
Big O(n*n): Verschachtelte Schleifen
Big O(n): Proportional
Big O(log n): Teile und herrsche
Big O(1): Konstante

O(n!) passiert normalerweise, wenn wir absichtlich schlechten Code schreiben.
O(n*n) ist ein schrecklicher Algo
O(n log n) ist akzeptabel und wird von bestimmten Sortieralgorithmen verwendet
O(n): Akzeptabel
O(log n), O(1) : Am besten

Die räumliche Komplexität ist für alle DS, d. h. O(n), nahezu gleich.
Die Raumkomplexität variiert von O(n) bis O(log n) oder O(1) mit Sortieralgorithmen

Die zeitliche Komplexität variiert je nach Algorithmus

Die beste Zeitkomplexität für Sortierungen mit Ausnahme von Zahlen wie Zeichenfolgen ist O(n log n), was bei Schnell-, Zusammenführungs-, Zeit- und Heap-Sortierungen der Fall ist.

Der beste Weg, das Gelernte anzuwenden, besteht darin, so viel wie möglich zu programmieren.

Auswahl des DS, der in welcher Problemstellung ausgewählt werden soll, basierend auf den Vor- und Nachteilen jedes DS.

Weitere Informationen finden Sie unter: bigochheatsheet.com

Das obige ist der detaillierte Inhalt vonEinführung in DSA und Big-O-Notation. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!