常见的算法时间复杂度从小到大排序如下：

常数级时间复杂度— O(1)

读取一个固定长度数组中的某个元素，只需要一步操作就能完成，因此时间复杂度为 O(1)

// 访问数组中的一个元素
const arr: number[] = [1, 2, 3, 4, 5]
const i: number = 2
const x: number = arr[i] // 只需要一步就能完成，时间复杂度为O(1)

对数级时间复杂度— O(log n)

二分查找，每次查找可以将区间缩小一半，因此时间复杂度为 O(log n)

// 二分查找
function binarySearch(arr: number[], target: number): number {
  let left: number = 0
  let right: number = arr.length - 1
  while (left <= right) {
    const mid: number = Math.floor((left + right) / 2)
    if (arr[mid] === target) {
      return mid
    } else if (arr[mid] < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
  return -1
}

const arr: number[] = [1, 2, 3, 4, 5]
const target: number = 3
const index: number = binarySearch(arr, target) // 每次查找可以将区间缩小一半，时间复杂度为O(log n)

线性时间复杂度— O(n)

对一个长度为 n 的数组进行线性搜索，最坏情况下需要扫描全部 n 个元素，因此时间复杂度为 O(n)

// 线性搜索
function linearSearch(arr: number[], target: number): number {
  for (let i: number = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i
    }
  }
  return -1
}

const arr: number[] = [1, 2, 3, 4, 5]
const target: number = 3
const index: number = linearSearch(arr, target) // 最坏情况需要扫描全部n个元素，时间复杂度为O(n)

线性对数级时间复杂度 — O(nlogn)

归并排序，可以将一个长度为 n 的数组分成两个长度为 n/2 的子数组，然后递归地将其排序，每轮排序需要进行 O(n) 次操作，因此总的时间复杂度为 O(nlogn)

// 归并排序
function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) {
    return arr
  }
  const mid: number = Math.floor(arr.length / 2)
  const left: number[] = arr.slice(0, mid)
  const right: number[] = arr.slice(mid)
  return merge(mergeSort(left), mergeSort(right))
}

function merge(left: number[], right: number[]): number[] {
  const res: number[] = []
  let i: number = 0
  let j: number = 0
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      res.push(left[i])
      i++
    } else {
      res.push(right[j])
      j++
    }
  }
  while (i < left.length) {
    res.push(left[i])
    i++
  }
  while (j < right.length) {
    res.push(right[j])
    j++
  }
  return res
}

const arr: number[] = [5, 4, 3, 2, 1]
const res: number[] = mergeSort(arr) // 每轮排序需要进行O(n)次操作，总的时间复杂度为O(nlogn)

平方级时间复杂度—O(n^2)

冒泡排序，每次比较相邻两个元素的大小，需要进行 O(n^2) 次比较操作

// 冒泡排序
function bubbleSort(arr: number[]): number[] {
  for (let i: number = 0; i < arr.length - 1; i++) {
    for (let j: number = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return arr
}

const arr: number[] = [5, 4, 3, 2, 1]
const res: number[] = bubbleSort(arr) // 需要进行O(n^2)次比较操作，时间复杂度为O(n^2)

立方级时间复杂度— O(n^3)

Floyd 算法，用于计算所有节点之间的最短路径，需要进行 O(n^3) 次计算

// Floyd算法
function floyd(n: number, graph: number[][]): number[][] {
  const dist: number[][] = graph.slice()
  for (let k: number = 0; k < n; k++) {
    for (let i: number = 0; i < n; i++) {
      for (let j: number = 0; j < n; j++) {
        if (dist[i][j] > dist[i][k] + dist[k][j]) {
          dist[i][j] = dist[i][k] + dist[k][j]
        }
      }
    }
  }
  return dist
}

const graph: number[][] = [
  [0, 3, 8, Infinity, -4],
  [Infinity, 0, Infinity, 1, 7],
  [Infinity, 4, 0, Infinity, Infinity],
  [2, Infinity, -5, 0, Infinity],
  [Infinity, Infinity, Infinity, 6, 0]
]
const res: number[][] = floyd(graph.length, graph) // 需要进行O(n^3)次计算，时间复杂度为O(n^3)

不多项式级时间复杂度 — O(2^n)

汉诺塔问题，需要进行指数级别的计算，因此时间复杂度为 O(2^n)

// 汉诺塔问题
function hanoi(n: number, from: string, to: string, temp: string): void {
  if (n === 1) {
    console.log(`Move disk 1 from ${from} to ${to}`)
  } else {
    hanoi(n - 1, from, temp, to)
    console.log(`Move disk ${n} from ${from} to ${to}`)
    hanoi(n - 1, temp, to, from)
  }
}

hanoi(3, 'A', 'C', 'B') // 需要进行指数级别的计算，时间复杂度为O(2^n)