复杂度分析

发表于 | 更新于 | 分类于

复杂度分析

时间复杂度分析

  1. 只关注循环执行次数最多的一段代码

    1
    2
    3
    4
    5
    6
    7
    8
    function sum($n)
    {
        $sum = 0;
        for($i = 1; $i <= $n; $i++){
            $sum += $i;
        }
        return $sum;
    }

    只需要关注第4、5行代码，其他的都是常量执行时间，这个方法的时间复杂度是O(n)。

  2. 加法法则：总复杂度等于量级最大的那段代码的复杂度

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    function sum($n)
    {
        $sum_1 = 0;
        $sum_2 = 0;
        $sum_3 = 0;
        for($i = 1; $i <= 100; $i++){
            $sum_1 += $i;
        }

        for($i = 1; $i <= $n; $i++){
        	$sum_2 += $i;
        }

        for($i = 1; $i <= $n; $i++){
        	for($j = 1; $j <= $n; $j++){
    	    	$sum_3 += $i * $j;
    	    }
        }
        return $sum_1 + $sum_2 + $sum_3;
    }

    第6、7行代码的时间复杂度是常量执行时间，第10、11行代码的时间复杂度是O(n)，第14、15、16行代码的时间复杂度是O(n2)，所以这个方法的时间复杂度是O(n2)。

  3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码的复杂度的乘积

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    function sum($n)
    {
    	$sum = 0;
    	for($i = 1; $i <= $n; $i++){
        	$sum += f($i);
        }
        return $sum;
    }
    function f($n)
    {
        $sum = 0;
        for($i = 1; $i <= $n; $i++){
            $sum += $i;
        }
        return $sum;
    }

    如果f(\(n)的时间复杂度是常量，那sum(\)n)的时间复杂度就是O(n)，但是f(\(n)的时间复杂度是O(n)，所以sum(\)n)的时间复杂度是O(n2)。

    常见的时间复杂度实例分析

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

2x = n => x=log2n；该代码段执行log2n次，所以该代码段的时间复杂度是O(logn)

log3n = log32*log2n

最好、最坏、平均、均摊时间复杂度

1
2
3
4
5
6
7
8
9
function find($array ,$x)
{   
    foreach ($array as $key => $value) {
        if($value == $x){
            return $key;
        }
    }
    return -1;
}

最好情况时间复杂度 如果x是第一个元素，那就不用遍历剩下的元素了，时间复杂度是O(1)；

最坏情况时间复杂度如果x是最后一个元素，就要遍历整个数组，时间复杂度是O(n);

平均时间复杂度

  1. 如果x在数组0~n-1位置中和不在数组中的概率相等 \[ \frac{(1+2+3+···+n+n)}{(n+1)} = \frac{n(n+3)}{2(n+1)} \] ​ 平均时间复杂度是O(n)

  2. 如果x在数组中的概率是1/2，在数组中各个元素的概率相等，为1/2n \[ \frac{1}{2n}+\frac{2}{2n}+\frac{3}{2n}+···+\frac{n}{2n}+\frac{n}{2} = \frac{(3n+1)}{4} \]

    这个值叫加权平均时间复杂度或者期望时间复杂度为O(n)

均摊时间复杂度在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

空间复杂度

和时间复杂度的分析方法一样