算法--复杂度

算法复杂度：

1. 时间复杂度：执行一个算法程序，所需要的时间

2. 空间复杂度：执行一个算法程序，所消耗计算机内存大小

时间复杂度

o（1）：

1. 常数阶，指的无论数据量如何递增，时间复杂度保持不变，典型的算法就是hash算法

2. n的值不管如何的变动，其算法执行次数都是3次，故这种时间恒定的就是常数阶

  <?php
        $sum = 0; $n = 3;
        $sum = ($n-1)*$n;
        echo $sum;

o（n）

1. 线性阶，指的是时间的复杂度会随着n的而线性增长。

2. 下面的代码的时间复杂度是o（n），因为代码的执行次数会执行n次，公式 times = n；比例为1；

    <?php
        for($i = 0; $i < $n; $i++) {
        }

o（logn）

1. 对数阶，如n=256，则算出为o（8），算法执行的次数为8次。

2. 如下所示，2^x= n，推出 x = log2^n，所以当n设定为256的时候，while循环执行程序需要8次。

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

o（n^2）

1. 平方阶，通常指的都是双重循环

2. 如下，时间复杂度就是o（n*n）

    for ($i = 0; $i < $n; $i++) {
        for($j = 0; $j < $n; $j++) {
        }
    }

3. 如下 时间的复杂度为o(m*n)

    for ($i = 0; $i < $m; $i++) {
        for($j = 0; $j < $n; $j++) {
        }
    }

4. 如下，涉及到等差数列的计算，算法执行的总次数 = n + （n-1）+ （n-2）+ .. +1 = n(n+1)/2 = n^2/2+1/2*n。我们在推导o阶函数的时候：第一没有常数不考虑；第二保持最高阶的项，故保持n^2/2；第三去除系数；所以最终算法的复杂度还是o(n^2)

    for ($i = 0; $i < $n; $i++) {
        for($j = 0; $j < $n-$i; $j++) {
        }
    }

常见的时间复杂度

    阶                非正式术语
    O(1)             常数阶  
    O(n)             线性阶
    O(n2)            平方阶
    O(logn)          对数阶
    O(nlogn)         nlogn阶
    O(n3)            立方阶
    O(2n)            指数阶

    常用的时间复杂度所耗费的时间从小到大依次是：
    O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

算法空间复杂度

1. 算法的空间复杂度通过计算算法所需的存储空间实现
2. 算法空间复杂度的计算公式：S(n) = O(f(n)),其中 n 为问题的规模，f(n)为语句关于 n 所占存储空间的函数。

总结

1. 算法是解决特定问题求解步骤的描述，在计算机中为指令的有限序列，并且每条指令表示一个或多个操作。
2. 算法的特性：有穷性、确定性、可行性、输入、输出。
3. 算法的设计要求：正确性、可读性、健壮性、高效率和低存储量需求。

本作品采用《CC 协议》，转载必须注明作者和本文链接