Basics - 算法时间复杂度和空间复杂度的计算

算法

算法，即解决问题的方法。同一个问题，使用不同的算法，虽然得到的结果相同，但是耗费的时间和资源是不同的。 就比如要拧一个螺母，使用扳手还是钳子是有区别的，虽然使用钳子也能拧螺母，但是没有扳手好用。

“条条大路通罗马”，解决问题的算法有多种，这就需要判断哪个算法“更好”

算法 / 程序

很多人误以为程序就是算法，其实不然，算法是解决某个问题的想法、思路，而程序是在心中有算法的前提下编写出来的可以运行的代码。

例如，要解决依次输出一维数组中的数据元素的值的问题，首先想到的是使用循环结构（ for 或者 while ），在有这个算法的基础上，开始编写程序。

算法相当于是程序的雏形，当解决问题时首先心中要有解决问题的算法，围绕算法编写出程序代码。

有算法不一定能解决问题

对于一个问题，想出解决的算法，不一定就能解决这个问题。

例如拧螺母，扳手相对于钳子来说更好使（选择算法的过程），但是在拧的过程（编写程序的过程）中发现螺母生锈拧不动，这时就需要另想办法。为了避免这种情况的发生，要充分全面地思考问题，尽可能地考虑到所有地可能情况，慎重选择算法。

“好”算法的标准

对于一个问题的算法来说，之所以称之为算法，首先它必须能够解决这个问题，称为准确性。其次，通过这个算法编写的程序要求在任何情况下不能崩溃，称为健壮性。

如果准确性和健壮性都满足，接下来还要考虑最重要的一点：通过算法编写的程序，运行的效率怎么样。

运行效率体现在两方面：

1. 算法的运行时间（称为“时间复杂度”）
2. 运行算法所需的内存空间大小（称为“空间复杂度”）

好算法的标准就是：在符合算法本身的要求的基础上，使用算法编写的程序运行的时间短，运行过程中占用的内存空间少，就可以称这个算法是“好算法”。

调查表明，人们对于软件或者 APP 的运行效率有极高的要求，例如对于网页打开的忍耐极限是 6 秒甚至更短，如果你设计的网页打开的时间超过 6 秒，多数人会在 4 秒甚至 3 秒的时候毫不犹豫地关掉而去浏览其他网页。在这个大背景下，一个好的“算法”更注重的是时间复杂度，而空间复杂度只要在一个合理的范围内就可以了，Google就是这么做的。

时间复杂度

计算一个算法的时间复杂度，不可能把所有的算法都编写出实际的程序出来让计算机跑，这样会做很多无用功，效率太低。实际采用的方法是估算算法的时间复杂度。

程序由三种结构构成：顺序结构、分支结构和循环结构。顺序结构和分支结构中的每段代码只运行一次；循环结构中的代码的运行时间要看循环的次数。

由于是估算算法的时间复杂度，相比而言，循环结构对算法的执行时间影响更大。所以，算法的时间复杂度，主要看算法中使用到的循环结构中代码循环的次数（称为“频度”）。次数越少，算法的时间复杂度越低。

例如：

// A
++x; s=0;
// B
for (int i=1; i