Chapter 1 Algorithm introduction

Binary search

Find elements from an ordered list of elements; Take the middle number each time and determine the size of the target element, eliminate half of the data, and then compare the new middle number from the rest of the list until the target element is found.

function numSearch(arr, target) {
    let low = 0,
        high = arr.length - 1,
        mid, midNum
    while (low <= high) {
        mid = Math.ceil((low + high) / 2)
        midNum = arr[mid]
        if (target == midNum) {
            return mid
        } else if (target < midNum) {
            high = mid - 1
        } else {
            low = mid + 1}}return null
};
Copy the code

Big O notation

Represents the growth of the algorithm’s runtime as the list grows, measured in terms of growth rather than seconds. For example, suppose the list contains n elements. Simple lookups require checking each element and run O(n) (linear time); Binary lookup, on the other hand, requires checking rows log n times, running in order log n (log time).

The big O notation indicates the worst-case running time.

Chapter 2 Selection sorting

Arrays and linked lists

  • Arrays: The memory space for storing data is contiguous, and each element has an index starting from 0. (Support random access)
  • Linked list: Each element stores the address of the next element, so that a series of random memory addresses are strung together; (Sequential access is supported)

Sequential access means reading elements one by one, starting with the first element, and random access means jumping straight to the tenth element.

Operational run time

An array of The list
read O(1) O(n)
insert O(n) O(1)
delete O(n) O(1)

Second, selection sort

Loop through the list to find the largest number and add that number to a new list until all numbers are arrayed. Running time is order n times n.

function findSmallest(arr) { // Find the smallest number in the array
    let smallest = arr[0] // Store the smallest value
    let smallest_index = 0 // Stores the index of the smallest element
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < smallest) {
            smallest = arr[i]
            smallest_index = i
        }
    }
    return smallest_index
}

function selectionSort(arr) {// Sort the array
    let newArr = [],smallest
    for(let i = 0; i < arr.length; i++){
        smallest = findSmallest(arr) // Find the smallest element in the array and add it to the new array
        newArr.push(arr[smallest])
        arr.splice(smallest,1)}return newArr
}
Copy the code

Chapter 3 Recursion

First, the recursive

Recursion is the function calling itself to make the solution clearer.

When writing a recursive function, you must tell it when to stop recursing. Every recursive function has two parts: a baseline condition and a recursive condition. A recursive condition refers to a function calling itself, while a baseline condition refers to a function not calling itself anymore, thus avoiding an infinite loop.

/ / recursion
function countdown(i){
    if(i<=0) {// Baseline conditions
        return
    }else{// recursive condition
        countdown(i-1)}}Copy the code

Second, the stack

A stack is a simple data structure with operations on and off the stack, operating on the topmost element. The computer internally uses a stack called a call stack. While using a stack is convenient, storing detailed information can take up a lot of memory. Each function call takes up a certain amount of memory, and if the stack is high, it means that the computer stores a lot of information about function calls.

Chapter 4 Quicksort

Divide and rule

Divide and conquer (D&C) is a well-known recursive problem-solving method that solves a problem by continually reducing the size of the problem. Because it’s a recursion, it also includes a baseline condition and a recursion condition.

D&C is not an algorithm that can be used to solve problems, but a way of thinking about solving problems.

Take the example of calculating the sum of arrays:

Two, quicksort use

Quicksort is solved using D&C, and the baseline condition is that the array is empty or contains only one element.

  • When an array is empty or of length 1, simply return the array as it is — no sorting at all;
  • If the array length is 2, determine the size of the two elements and swap places;
  • When the array length is 3, decompose the array until the baseline condition is satisfied.

How quicksort works:

  1. Select an element from the array, called a reference value;
  2. Partition – Find elements smaller than the base value and elements larger than the base value, divided into two subarrays and a base value;
  3. Recursion is used to sort subarrays quickly.
  4. Merge the results to get an ordered array.
function quicksort(arr){
    let len = arr.length
    if(len<2) {return arr
    }else{
        let pivot = arr[0]
        let less=[],greater=[]
        for(let i=1; i<len; i++){if(arr[i]<pivot){
                less.push(arr[i])
            }else{
                greater.push(arr[i])
            }
        }
        return quicksort(less).concat([pivot],quicksort(greater))
    }
}
Copy the code

If quicksort runs O(n log n) on average, it runs O(n*n) in the worst case.

Average case and worst case

Quicksort performance is highly dependent on the base value you choose.

The array is not split in half; Instead, one of the subarrays is always empty, which results in a very long call stack, which is the worst case; Running time is order n times n.

This array splits the array in half every time, so you don’t need as many recursive calls, and you get to the baseline condition very quickly, so the call stack is much shorter, which is the best case; Running time is order log n times n.

The best case is also the average case. As long as you randomly select one array element each time as a reference value, the average running time for quicksort will be O(n log n).

Chapter 5 hash table

Hash function && hash table

Hash function: “map input to number”, map the same input to the same index, map different input to different index. The hash function knows how big the array is and returns only valid indexes.

Hash table: A data structure created using a combination of hash functions and arrays. Both arrays and linked lists are mapped directly into memory, but hash tables are more complex and use hash functions to determine where elements are stored. A hash table consists of keys and values.

Python provides a hash table implemented as a dictionary. You can use dict to create a hash table. In JavaScript, hash tables can be represented by objects containing multiple attributes.

Second, the conflict

A conflict is when two keys are assigned the same position;

The easiest way to handle collisions is to store a linked list at the same location if two keys map to the same location.

Ideally, hash functions map keys evenly to different locations in the hash table, and good hash functions rarely cause collisions. Otherwise, if the hash table stores a long linked list, the speed of the hash table will decrease dramatically.

On average, hash tables take O(1) for all operations, meaning it takes the same amount of time to fetch an element from an array no matter how big it is.

Three, the filling factor

The fill factor = hash percentage/total number of hash positions. The fill factor measures how many hash positions are empty.

Suppose you want to store the prices of 100 items in a hash table that contains 100 locations. In the best case, each item will have its own place, and the hash will have a fill factor of 1. In general, once the fill factor is greater than 0.7, you need to adjust the hash table length, usually doubling the array.

You need to use the hash function to insert all the elements into the new hash table. Good hash functions distribute the values evenly across the array. And good hash function implementation, can understand SHA function.