Skip to content
On this page

算法基础

线性结构

  • 线性结构是一个有序数据元素的集合

常用的线性结构有:一维数组,栈(堆栈),队列,双队列,线性表

常见的非线性结构有:多维数组,广义表,树(二叉树等)

时间复杂度

复杂度:简单 --> 复杂

  • O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

标准: n^2 想办法优化成 n log n

复杂度代码示例

js
// O(1)
let n = 1
console.log(n)

// O(n) 一层循环,每个遍历
for(let i = 0; i <= n; i++) {
  console.log(i)
}

// O(logn) 对数形式
for(let i = 0; i <= n; i=i*2) {
  console.log(i)
}

// O(n^2) 循环嵌套,x个则复杂度为 O(n^x)
for(let i = 0; i <= n; i++) {
  for(let j = 0; i <= n; j++) {
    console.log(i, j)
  }
}
// O(1)
let n = 1
console.log(n)

// O(n) 一层循环,每个遍历
for(let i = 0; i <= n; i++) {
  console.log(i)
}

// O(logn) 对数形式
for(let i = 0; i <= n; i=i*2) {
  console.log(i)
}

// O(n^2) 循环嵌套,x个则复杂度为 O(n^x)
for(let i = 0; i <= n; i++) {
  for(let j = 0; i <= n; j++) {
    console.log(i, j)
  }
}

不同复杂度计算趋势

image

常见算法复杂度

image

image