算法的时间复杂度&空间复杂度

算法的衡量指标：在正确性的前提下，重点关注以下指标:

    （1）时间性能——运行算法所需的时间开销。

    （2）空间性能——运行算法所需的辅助空间的规模。

    （3）其它性能——如可读性/可移植性等。

---

时间复杂度

时间性能（时间复杂度）的描述方法讨论：

     方式(1)： 以运行算法的机器时间开销来度量

        问题：与具体机器相关，难以比较

     方式（2）：以算法中语句的执行次数来衡量

        问题：计算麻烦，可以简化为

     方式（3）：以算法中语句的执行次数的数量级来替代。    √  

数量级：如果变量n的函数f(n)和g(n)满足：

             lim f(n)/g(n)=常数 k (k≠∞,0)，

             则称f(n)和g(n) 是同一数量级的，

            并用f(n)=O(g(n))的形式来表示。

较为常见的算法的时间复杂度从小到大依次如下：

例：求解以下程序段的时间复杂度：

        for（i=1; i<=n; i++）x=x+1;

        该语句的流程图如下:

由此可知，数量级为：limf(n)/g(n)= lim(3n+2)/n = 3，

相应的时间复杂度为为O (n)

---

空间复杂度

——计算方法类似时间复杂度