时间：   |   分类：     |   阅读： 882 字 ~2分钟
  1. 1. 前情提要
  2. 2. 参考
  3. 3. 时间复杂度
    1. 3.1. 计算时间复杂度
      1. 3.1.1. 完整例子
    2. 3.2. 常见时间复杂度
      1. 3.2.1. 常数阶
      2. 3.2.2. 对数阶
      3. 3.2.3. 线性阶
      4. 3.2.4. 线性对数阶
      5. 3.2.5. 平方立方阶
      6. 3.2.6. 指数阶
  4. 4. 空间复杂度
    1. 4.1. 常见空间复杂度
    2. 4.2. 常数阶
    3. 4.3. 线性阶
    4. 4.4. 平方立方阶

1. 前情提要

做LeetCode需要评估时间复杂度和空间复杂度.

只依稀时间复杂度跟循环次数相关.空间复杂度跟时间复杂度有点关系.

2. 参考

3. 时间复杂度

3.1. 计算时间复杂度

  • 找出基本语句:基本上都是最内层的循环
  • 计算基本语句的数量级
  • 计算O()
    1. 1代替所有的常熟
    2. 保留最高阶
    3. 去掉最高阶的常数

3.1.1. 完整例子

$a=1;                           //1次
for ($i=0; $i < $n; $i++) {     //n次
  $b=$i;                        //n次
  for ($j=0; $j <$n ; $j++) {   //n²次,如果这里是$m 那么就是m*n次.
    echo $i+$j;                 //n²次
  }
}
  • 2n²+2n+1:完整的次数
  • 2n²+2n:步骤1
  • 2n²:步骤2
  • n²:步骤3
  • O(n²)

3.2. 常见时间复杂度

从上到下,越来越复杂

  • 常数阶:O(1)
  • 对数阶:O(logN)
  • 线性阶:O(n)
  • 线性对数阶:O(nlogN)
  • 平方阶:O(n²)
  • 立方阶:O(n³)
  • K次方阶O(n^k)
  • 指数阶(2^n)
  • 阶乘:O(n!)
  • ??:O(n^n)

3.2.1. 常数阶

无论代码执行了多少行,只要是没有循环等复杂结构,那这个代码的时间复杂度就都是O(1)

$a=1;
$b=2;
//等等. //以上代码执行时间和n无关.

3.2.2. 对数阶

下面的代码需要执行log2的n次方次

$i=1;
while ($i <= $n) {
  $i*=2; //平方
}

//同样的如果是
while ($i <= $n) {
  $i*=5; //那就是以5为底的log
}

3.2.3. 线性阶

很简单就一个循环.并且和n相关

3.2.4. 线性对数阶

for($m=1; $m<$n; $m++)  //n次
{
    $i = 1;             //n次
    while($i<$n)
    {
        $i = $i * 2;    //n*logN次
    }
}

3.2.5. 平方立方阶

嵌套两次和嵌套三次

3.2.6. 指数阶

$a=0;
function feb($i){
  ++$a;
  if ($i<=1) {
    return 1;
  }else{
    return feb($i-1)+feb($i-2);
  }
}
  • n==1:1次
  • n==2:3次
  • …
  • 这个就是$2^{n}$

4. 空间复杂度

空间复杂度是反映运行过程中临时空间大小的

4.1. 常见空间复杂度

  • S(1)
  • S(n)
  • S(n²)

4.2. 常数阶

没有循环,n无关

4.3. 线性阶

$arr=[0,1,2,3,4,5,6,7,8,.....n];
$temp=$arr;                       //n的内存空间
for($i=0;$i<count($arr);$i++){    //循环,但是只新开了一个 i的内存空间  1
  $j=$i;                          //同上,j的                        1
}
//综合起来就是S(n)

4.4. 平方立方阶

和空间复杂度差不多,每循环一次,产生一个新的变量.

$arr=range('a','z');                //n
foreach ($arr) as $value) {
  for($i=0;$i<count($arr);$i++) {   //1
    $name=$value.$arr[$i];
    $$name=$$name;                  //n平方
  }
}
0%