Pengenalan kepada Notasi DSA & Big O

Nota untuk menguasai DSA:

Sarjana DSA untuk "layak" menerima gaji bergaji tinggi yang ditawarkan kepada S/w Ers.
DSA ialah bahagian utama Kejuruteraan Perisian.
Sebelum menulis kod, pastikan anda memahami gambaran yang lebih besar dan kemudian menelusuri butirannya.
Semuanya tentang memahami konsep secara visual, dan kemudian menterjemahkan konsep tersebut kepada kod melalui mana-mana l/g kerana DSA adalah agnostik bahasa.
Setiap konsep yang akan datang entah bagaimana dikaitkan dengan konsep sebelumnya. Oleh itu, jangan melompat topik atau bergerak ke hadapan melainkan anda telah menguasai konsep tersebut secara menyeluruh dengan mempraktikkannya.
Apabila kita mempelajari konsep secara visual, kita mendapat pemahaman yang lebih mendalam tentang bahan yang seterusnya membantu kita mengekalkan pengetahuan untuk tempoh yang lebih lama.
Jika anda mengikut nasihat ini, anda tidak akan rugi.

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

Non-linear DS:
Trees
Graphs

Notasi O Besar

Adalah penting untuk memahami notasi ini untuk perbandingan perf algo.
Ini adalah cara matematik untuk membandingkan kecekapan algo.

Kerumitan Masa

Lebih cepat kod dijalankan, semakin rendah ia
V. impt untuk kebanyakan temu bual.

Kerumitan Ruang

Dianggap jarang berbanding kerumitan masa kerana kos penyimpanan yang rendah.
Perlu difahami, kerana penemuduga mungkin meminta anda daripada perkara ini juga.

Tiga Huruf Yunani:

1. Omega
2. Theta
3. Omicron iaitu Big-O [paling kerap dilihat]

Kes untuk algo

1. Kes terbaik [diwakili menggunakan Omega]
2. Purata kes [diwakili menggunakan Theta]
3. Kes terburuk [diwakili menggunakan Omicron]

Secara teknikal tiada kes terbaik bagi purata kes Big-O. Mereka dilambangkan menggunakan omega & theta masing-masing.
Kami sentiasa mengukur kes terburuk.

## 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.

Perbandingan Kerumitan Masa untuk n=100:

O(1) = 1
O(log 100) = 7
O(100) = 100
O(n^2) = 10,000

Perbandingan Kerumitan Masa untuk n=1000:

O(1) = 1
O(log 1000) = ~10
O(1000) = 1000
O(1000*1000) = 1,000,000

Terutamanya kami akan memberi tumpuan kepada 4 ini:
O(n*n): Gelung Bersarang
O(n): Berkadar
Big O(log n): Bahagi & takluk
O besar(1): Malar

O(n!) biasanya berlaku apabila kita sengaja menulis kod buruk.
O(n*n) sungguh mengerikan Algo
O(n log n) boleh diterima dan digunakan oleh algo pengisihan tertentu
O(n) : Boleh diterima
O(log n), O(1) : Terbaik

Kerumitan ruang hampir sama untuk semua DS iaitu O(n).
Kerumitan ruang akan berbeza dari O(n) hingga O(log n) atau O(1) dengan mengisih algo

Kerumitan masa ialah apa yang berbeza-beza berdasarkan algo

Kerumitan masa terbaik untuk mengisih selain nombor seperti rentetan ialah O(n log n) yang terdapat dalam Quick, Merge, Time, timbunan isihan.

Cara terbaik untuk menerapkan pembelajaran anda adalah dengan mengekod sebanyak yang anda boleh.

Memilih DS yang hendak dipilih dalam pernyataan masalah berdasarkan Kebaikan-Keburukan setiap DS.

Untuk maklumat lanjut, rujuk: bigocheatsheet.com

Atas ialah kandungan terperinci Pengenalan kepada Notasi DSA & Big O. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!