算法初探

复杂度指标

• O (1): 常数复杂度 - Constant Complexity
• O (log n): 对数复杂度 - Logarithmic Complexity
• O (n): 线性复杂度 - Linear Complexity
• O (n^2): 平方复杂度 - N square Complexity
• O (2^n): 指数 - Exponential Growth
• O (n!): 阶乘 - Factorial

时间复杂度

通过分析函数，根据 n 的不同情况看其运行次数，然后得出一个平均的运行次数量级

例子

O(1): 常数复杂度

常数阶的复杂度，这种复杂度无论数据规模n如何增长，计算时间是不变的

let n = 10
console.log('Hello world' + n)

O(n): 线性复杂度

线性复杂度，随着数据规模n的增长，计算时间也会随着n线性增长。

for (let i = 1; i <= n; i++) {
  console.log("Hello world " + i)
}

O(n^2): 平方复杂度

平方级复杂度，典型情况是当存在双重循环的时候，即把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了

for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= n; j++) {
  	console.log("Hello world" + i + " and " + j)
  }
}

O(log n): 对数复杂度

对数复杂度，随着问题规模n的增长，计算时间也会随着n对数级增长。

for (let i = 1; i < n; i = i * 2) {
  console.log("Hello world" + i);
}