Time complexity/Extra space complexity (O)

Recursive behavior and time complexity estimation

• Recursive behavior:

  Recursive behavior is actually a process of pushing the stack. It puts a process that cannot obtain a specific value on the stack one by one until the specific value is obtained, and then executes the saved process in the way of pushing out the stack. If the process that cannot be obtained is encountered again, the above process is repeated until the stack is empty and the specific value is returned.

• Time complexity estimation:

  Master formula: T(N) = a*T(N/b) + O(N^d)

  A: How many subprocesses are involved in a process

  There are three results:

  1. Log (b,a) > d -> complexity O(N^log(b,a))
  2. Log (b,a) = d -> N (N^d * logN)
  3. Log (b,a) < d -> complexity O(N^d)

  Example: merge sort/quicksort

Sorting algorithm

Time complexity (O(N^2))

Bubble sort

Compare adjacent numbers in pairs, in order from smallest to largest or from largest to smallest.

const bubbleSort = (arr) = > {
  for (let i = 0; i < arr.length; i += 1) {
    let temp
    for (let j = 0; j < arr.length - i - 1; j += 1) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}

// Sort for a given range
const bubbleRangeSort = (arr, L, R) = > {
  if (L >= R) return arr 
  if (L < 0) L = 0
  if (R > arr.length - 1) R = arr.length - 1
    for (let i = L; i < R + 1; i += 1) {
      let temp
      for (let j = L; j < R - (i - L); j += 1) {
        if (arr[j] > arr[j + 1]) {
          temp = arr[j]
          arr[j] = arr[j + 1]
          arr[j + 1] = temp
        }
      }
    }
    return arr
  }

Copy the code

Selection sort

Find the smallest of all the sequences and place it in the first place. Then look at the smallest remaining element and put it in the second position… And so on

const chooseSort = (arr) = > {
  for(let i = 0; i< arr.length - 1; i+=1) {
    let temp = arr[i] 
    for(let j = i + 1; j< arr.length; j+=1) {
      if (temp > arr[j]) {
        arr[i] = arr[j]
        arr[j] = temp
      }
    }
  }
  return arr
}

Copy the code

Insertion sort

Insert a record into an already ordered table to form an ordered table

const insertSort = (arr) = > {
  for(let i = 0; i < arr.length; i+=1) {
    for(let j = 0; j < i; j+=1) {
      if (arr[i] < arr[j]) {
        let temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
      }
    }
  }
  return arr
}

Copy the code

Time complexity (O((N*logN))

Strengthen your understanding of the problem

Small and questions:

Problem: In an array, the sum of the numbers to the left of each number less than the current number is called the small sum of the array. Find the small sum of an array.

The middle line is divided into the smallest element (formal binary tree), the small sum before the group, and the small sum of the front and back branches.

Answer:

const smallSum = (arr) = > {
  if (arr === undefined || arr === null || arr.length < 2) {
    return arr
  }
  return PartSmallSum(arr, 0 , arr.length - 1)}const PartSmallSum = (arr, L, R) = > {
  if (L === R) return 0
  const middle = Math.floor(L + ((R - L) >> 1))
  return PartSmallSum(arr, L, middle) + PartSmallSum(arr, middle + 1, R) + margeSmallSum(arr, L, middle, R)
}

// find the sum *
const margeSmallSum = (arr, L, middle, R) = > {
  let help = new Array(R - L + 1)
  let i = 0
  let pl = L
  let pr = middle + 1
  let res = 0

  while(pl <= middle && pr <= R) {
    res += arr[pl] < arr[pr] ? arr[pl]*(R-pr+1) : 0 
    help[i++] = arr[pl] < arr[pr] ? arr[pl++] : arr[pr++]
  }
  while(pl <= middle) {
    help[i++] = arr[pl++]
  }

  while(pr <= R) {
    help[i++] = arr[pr++]
  }

  for(let i = 0; i < help.length; i+=1) {
    arr[L + i] = help[i]
  }
  return res
}

Copy the code

Dutch question:

Problem: Given an array arr and num, place the number less than num on the left, the number equal to num in the middle, and the number greater than num on the right.

If the first number is greater than num, swap it with the last number. If the first number is smaller than num, swap it with the previous number.

Answer:

const flagQuestion = (arr, num) = > {
  if (arr === null || arr === undefined || arr.length < 2) {
    return arr
  }
  let cur = 0
  let pl = 0
  let pr = arr.length -1
  while (cur <= pr) {
    if (arr[cur] > num) {
      arr = changePosition(arr,cur,pr--)
    }
    if (arr[cur] < num) {
      changePosition(arr,cur++,pl++)
    }
    if (arr[cur] === num) {
      cur++
    }
  }
  return arr
}

const changePosition = (arr, l, r) = > {
  if (l === r) return arr
  const temp = arr[l]
  arr[l] = arr[r]
  arr[r] = temp
  return arr
}
Copy the code

Merge sort

Ideas: As shown in small and

const mergeSort = (arr) = > {
  if (arr === undefined || arr === null || arr.length < 2) {
    return arr
  }
  return partMergeSort(arr, 0 , arr.length - 1)}const partMergeSort = (arr, L, R) = > {
  if (L === R) return arr
  const middle = Math.floor(L + ((R - L) >> 1))
  arr = partMergeSort(arr, L, middle)
  arr = partMergeSort(arr, middle + 1, R)
  arr = margePart(arr, L, middle, R)
  return arr
}

const margePart = (arr, L, middle, R) = > {
  let help = new Array(R - L + 1)
  let i = 0
  let pl = L
  let pr = middle + 1

  while(pl <= middle && pr <= R) {
    help[i++] = arr[pl] < arr[pr] ? arr[pl++] : arr[pr++] / / [3]
  }
  while(pl <= middle) {
    help[i++] = arr[pl++]
  }

  while(pr <= R) {
    help[i++] = arr[pr++]
  }

  for(let i = 0; i < help.length; i+=1) {
    arr[L + i] = help[i]
  }
  return arr
}

Copy the code

Quick sort (random long term is O((N*logN), non-random may be O(N^2))

The Dutch flag, for example

const quickSort = arr= > {
  if (arr === null || arr === undefined || arr.length < 2) {
    return arr
  }
  return mergePartition(arr, 0, arr.length - 1)}const mergePartition = (arr, l, r) = > {
  if (l < r) {
// Plus random quicksort
    arr = changePosition(arr, l + Math.floor(Math.random() * (r - l + 1)), r)
    const p = partition(arr, l, r)
    arr = p.arr
    arr = mergePartition(arr, l, p.l - 1)
    arr = mergePartition(arr, p.more + 1, r)
  }
  return arr
}

const partition = (arr, l, r) = > {
  // Divide by the last number
  let cur = l
  let more = r - 1
  while (cur <= more) {
    if (arr[cur] > arr[r]) {
      arr = changePosition(arr, cur, more--)
    }
    if (arr[cur] < arr[r]) {
      arr = changePosition(arr, cur++, l++)
    }
    if (arr[cur] === arr[r]) {
      cur++
    }
  }
  arr = changePosition(arr, ++more, r)
  return { arr, l, more }
}

const changePosition = (arr, l, r) = > {
  if (l === r) return arr
  const temp = arr[l]
  arr[l] = arr[r]
  arr[r] = temp
  return arr
}
Copy the code