评价算法优劣的标准：
时间复杂度、额外空间复杂度、常数操作

常数操作

这部分操作的执行时间与样本量无关，每次执行时间固定。

常见的常数操作：

  • 算术运算：+ - * / %
  • 位运算：>> >>> << | & ^

    • 带符号右移, 空缺位置用符号位补，负数 1000… ，右移 1100…

    • 不带符号位右移，都用 0 补

  • 赋值、比较、自增、自减
  • 数组寻址

时间复杂度

衡量在整个流程中发生了多少次常数操作。

如何确定表达式：

  • 想象该算法流程处理的最差情况
  • 整个流程拆分为一个个常数操作
  • 数据量为 N，看常数操作数量和 N 是什么关系

如何确定时间复杂度：

  • 表达式忽略掉所有常数项，只取最高阶。
  • O(忽略系数的高阶项)

    额外空间复杂度

    如果流程只需要定义有限个变量，变量数量与样本数无关，那么空间复杂度为 O(1)
    如果要开辟一个额外数组，该空间不是功能要求的，那么空间复杂度为 O(N)

其他

刷题中的最优解

先保证时间复杂度最低，然后尽量降低空间复杂度。