算法基础

线性结构

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

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

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

时间复杂度

复杂度：简单 --> 复杂

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

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

复杂度代码示例

// 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)
  }
}

不同复杂度计算趋势

常见算法复杂度