算法学习笔记

一、时间复杂度和空间复杂度

1.时间复杂度

时间复杂度用Big O notation表示,看执行次数。

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

注意:只看最高复杂度的运算,不关心常数系数。

2.空间复杂

  1. 数组的长度
    一维数组,长度为n,则空间复杂度为O(n),
    二维数组,长度为n^2,则空间复杂度为O(n^2)。
  2. 递归的深度
    递归最深的深度,为空间复杂度的最大值。
  3. 数组+递归
    空间复杂度为两者之间的最大值。

你可能感兴趣的