时空复杂度

· · 个人记录

时间复杂度&空间复杂度

一.大O的渐进表示法

  1. 所有常数都用常数1表示；
  2. 只保留最高阶项；
  3. 如果最高阶项存在且不是1，则去除与这个项的系数，得到的结果就是大O阶。

注：若刷题时遇到题目要求时间复杂度为O(1)的，并不是要求函数内部不能有循环，而是要求循环的次数为常数次。

二.时间复杂度（基本定义）

一个算法所花费的时间与其中语句的执行次数成正比例，所以算法中的基本操作的执行次数既为算法的时间复杂度。

二.空间复杂度（基本定义）

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，算的是变量的个数。

注：递归算法的空间复杂度通常是递归的深度（即递归多少层）。