怎么计算时间和空间复杂度？

序

通常大家衡量一段算法算法的好坏，一般都是用时间复杂度和空间负杂度来作考量指标。
那么如果有一段代码，我要如何计算它的时间复杂度和空间复杂度是多少呢？

时间复杂度

大O复杂度表示法

算法的执行效率，粗略的讲，就是执行代码所需要的时间。多行代码时，所有代码执行时间等于每行代码执行时间相加。
也就是每行代码执行时间越久，总时间也就越久。即：总执行时间与每行代码的执行时间成正比。

在数学中，O表示正比的意思。所以可得：

T(n) = O(f(n))

大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

时间复杂度分析三个方法

只关注循环次数最多的一行代码

这个不难理解。在无限大的场景下，n+1+2+3+4与n没什么区别，所以我们只要关注n就行。

加法法则

因为总的代码执行次数是每一行代码执行次数相加得来的。所以求总的时间复杂度大可以将每一行代码复杂度都算出来，然后相加。再通过法一，取其中最复杂的一行代码的复杂度。
如：n+2n+n²+1。其实就可以先简化为3n+n²+1，再通过方法一，得时间复杂度为O(n²)。

总结成公式：
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；
那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))。

乘法法则

乘法法则一般用于嵌套的情况。在嵌套代码下，复杂度等于嵌套内外代码复杂度的乘集。

这里举一个简单的例子：

function a(n) {
    $ret = 0; 
    for ($i = 1; $i < n; ++$i) {
        $ret = $ret + b($i);
    } 
} 
 
function b(n) {
    $sum = 0;
    for ($i = 1; $i < $n; ++$i) {
        $sum = $sum + $i;
    } 
    return $sum;
}

首先我们看b函数，由方法一、方法二可以得b函数的时间复杂度为O(n)。
然后a函数，如果a函数中的b函数只是一个常量的话，a函数的时间复杂度也是O(n)。
但是由于在a函数中调用了b函数，所以应该按乘法法则来计算。即时间复杂度为：O(n) * O(n) = O(n²)

需要注意的复杂度

O(1)

通常我们把常量级的时间复杂度称为O(1)。举个例子：

 $i = 8;
 $j = 6;
 $sum = $i + $j;

在上面这个例子中，虽然三行代码一共执行了3次，时间复杂度也不是O(3)，而是O(1)。

O(logn)、O(nlogn)

对数阶时间复杂度非常常见，但却也是最难分析的一种。具体要怎么计算时间复杂度呢？我们先举个例子：

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

根据我们之前讲的分析法，显然是第三行是执行最多次，我们只要计算第三行时间复杂度就可以。

当变量$i的值从1开始，每循环一次乘以2，直到大于n时，循环结束。很明显这就是一个等比数列。

2^0  2^1  2^2  2^3 ... 2^k ... 2^x = n

所以我们只要直到x的值是多少，就可以知道，执行了多少次了。
通过2^x=n，求解：x=log₂n。所以这段代码的时间复杂度为O(log₂n)。

我们把这段代码再改一下。

$i=1;
while ($i <= $n)  {
    $i = $i * 3;
}

根据刚刚的思路，这段代码的时间复杂度为O(log₃n)。

我们知道，在数学中，对数是可以转换的。log₃n = log₃2 * log₂n。
又，log₃2为一个常量。根据分析方法，常量可以忽略。

即可得结论：在对数阶时间复杂度的计算中，我们可以忽略对数的"底"，统一表示为：O(logn)。

再加上之前的乘法法则，如果我们在复杂度为O(n)的代码中，调用复杂度为O(logn)的函数，既可得复杂度为：nO(logn)。

O(m+n)、O(m*n)

还有一种特殊的时间复杂度情况。代码的复杂度由两个数据的规模来决定。

funtion a($m, $n) {
    $sum_1 = 0;
    for ($i = 1; $i < $m; ++$i) {
        $sum_1 = $sum_1 + $i;
    }
    
    $sum_2 = 0;
    for ($j = 1; $j < $n; ++$j) {
        $sum_2 = $sum_2 + $j;
    }

  return $sum_1 + $sum_2;
}

在上面代码中，因为我们无法确定m和n到底谁大，所以我们不能简单的省略其中一个。所以时间复杂度就是O(m+n)了。
同理，O(m*n)也一样。

空间复杂度

前面我们提到，时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。

类比一下：

空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。

举个例子：

funtion test(n) {
    $arr = [];
    for ($i = 0; $i <$n; ++$i) {
        $a[] = $i * $i;
    }
    
    for ($i = $n-1; $i >= 0; --$i) {
        echo $a[$i];
    }
}

跟时间复杂度分析一样，我们一行一行往下看。可以看到，我们申请了一个空间变量$i和一个数组$arr。除此之外，其他代码都没有占用多少空间。当循环执行完，$arr中有了n个元素。即可得：整段代码的空间复杂度就是：O(n)。

xpblog

序