算法与数据结构1

评估算法优劣的核心指标是什么?

  • 时间复杂度(流程决定) 最重要
  • 额外空间复杂度(流程决定)
  • 常数项时间(实现细节决定) 最后考虑

常数时间时间操作

  • 常见算术运算
  • 位运算(>>,>>>,<<,<<<,|,&,^)
  • 赋值、比较、自增、自减
  • 数组寻址

时间复杂度

常数时间的操作
确定算法流程的总操作数量与样本数量之间的表达式关系
只看表达式最高阶项的部分

每次拆分必须拆到常数级别

额外空间复杂度

作为输入参数的空间,不算额外空间。
作为输出结果的空间,也不算额外空间。

算法流程的常数项

时间复杂度只是一个很重要的指标而已。如果两个时间复杂度一样的算法,你还要去在时间上拼优劣,就进入到拼常数时间的阶段,简称拼常数项。

常见的时间复杂度

排名从好到差:

O(1)
O(logN)
O(N)
O(N*logN)
O(N^2) O(N^3) … O(N^K)
O(2^N) O(3^N) … O(K^N)
O(N!)

算法和数据结构学习的大脉络

  1. 知道怎么算的算法
  2. 知道怎么试的算法

异或

  1. 0^N == N N^N == 0
  2. 异或运算满足交换律和结合率

用无进位相加来理解

你可能感兴趣的