算法学习-时间复杂度和空间复杂度

对于解决一个问题来说，可以有很多种解决问题的算法。尽管算法不是唯一的，但是对于问题本身来说相对好的算法还是存在的，这里可能有人会问区分好坏的标准是什么？
这个要从「时效」和「存储」两方面来看。

人总是贪婪的，在做一件事的时候，我们总是期望着可以付出最少的时间、精力或者金钱来获得最大的回报，这个类比到算法上也同样适用，那就是花最少的时间和最少的存储做成最棒的解决办法，所以好的算法应该具备时效高和存储低的特点。这里的「时效」是指时间效率，也就是算法的执行时间，对于同一个问题的多种不同解决算法，执行时间越短的算法效率越高，越长的效率越低；「存储」是指算法在执行的时候需要的存储空间，主要是指算法程序运行的时候所占用的内存空间。

1、时间复杂度

我们的科学家前辈们发现当我们试图去用执行时间作为独立于具体程序或计算机的度量指标去描述一个算法的时候，确定这个算法所需要的步骤数目非常重要。如果我们把算法程序中的每一步看作是一个基本的计量单位，那么一个算法的执行时间就可以看作是解决一个问题所需要的总步骤数。
其实，上述我们还要考虑一个问题，这个每一步的计量单位又是不同的，所以如何选择呢？
看一个简单求和的例子：

def get_sum(n):
          sum = 0
   for i in range(1,n+1):
         sum += i
   return sum
print(get_sum(10))

（1）我们一般用一个叫 T 的函数来表示赋值语句的总数量，比如上面的例子可以表示成 T(n) = n + 1。这里的 n 一般指的是「数据的规模大小」，所以前面的等式可以理解为「解决一个规模大小为 n，对应 n+1 步操作步数的问题，所需的时间为 T(n)」。
（2）对于 n 来说，它可以取 10，100，1000 或者其它更大的数，我们都知道求解大规模的问题所需的时间比求解小规模要多一些，那么我们接下来的目标就很明确了，那就是「寻找程序的运行时间是如何随着问题规模的变化而变化」。

我们的科学家前辈们又对这种分析方法进行了更为深远的思考，他们发现有限的操作次数对于 T(n) 的影响，并不如某些占据主要地位的操作部分重要，换句话说就是「当数据的规模越来越大时，T(n) 函数中的某一部分掩盖了其它部分对函数的影响」。最终，这个起主导作用的部分用来对函数进行比较，所以接下来就是我们所熟知的大 O 闪亮登场的时间了。

2、大O表示法

【数量级】函数用来描述当规模 n 增加时，T(n) 函数中增长最快的部分，这个数量级函数我们一般用「大 O」表示，记做 O(f(n))。它提供了计算过程中实际步数的近似值，函数 f(n) 是原始函数 T(n) 中主导部分的简化表示。
在上面的求和函数的那个例子中，T(n) = n + 1，当 n 增大时，常数 1 对于最后的结果来说越来不越没存在感，如果我们需要 T(n) 的近似值的话，我们要做的就是把 1 给忽略掉，直接认为 T(n) 的运行时间就是 O(n)。

3、最好情况、最坏情况和平均情况

算法的运行时间不只是问题规模，还有具体的分析数据。
某个特定的数据集能让算法的执行情况极好，这就是最「最好情况」，而另一个不同的数据会让算法的执行情况变得极差，这就是「最坏情况」。不过在大多数情况下，算法的执行情况都介于这两种极端情况之间，也就是「平均情况」。因此一定要理解好不同情况之间的差别，不要被极端情况给带了节奏。
对于「最优情况」，没有什么大的价值，因为它没有提供什么有用信息，反应的只是最乐观最理想的情况，没有参考价值。「平均情况」是对算法的一个全面评价，因为它完整全面的反映了这个算法的性质，但从另一方面来说，这种衡量并没有什么保证，并不是每个运算都能在这种情况内完成。而对于「最坏情况」，它提供了一种保证，这个保证运行时间将不会再坏了，所以一般我们所算的时间复杂度是最坏情况下的时间复杂度，这和我们平时做事要考虑到最坏的情况是一个道理。

4、一些数量级函数

数量级函数
为了确定这些函数哪些在 T(n) 中占主导地位，就要在 n 增大时对它们进行比较，请看下图： 数量级函数比较

在上图中，我们可以看到当 n 很小时，函数之间不易区分，很难说谁处于主导地位，但是当 n 增大时，我们就能看到很明显的区别，谁是老大一目了然：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)

5、空间复杂度（目前不是要解决的主要问题）

类比于时间复杂度的讨论，一个算法的空间复杂度是指该算法所耗费的存储空间，计算公式计作：S(n) = O(f(n))。其中 n 也为数据的规模，f(n) 在这里指的是 n 所占存储空间的函数。
空间复杂度其实在这里更多的是说一下这个概念，因为当今硬件的存储量级比较大，一般不会为了稍微减少一点儿空间复杂度而大动干戈，更多的是去想怎么优化算法的时间复杂度。所以我们在日常写代码的时候就衍生出了用「空间换时间」的做法，并且成为常态。
最后说一点的是，估算算法的复杂度这件事你不要指望一下子看了一篇文章就想弄懂，这个还是要有意识的多练，比如看到一个程序的时候有意识的估算一下它的复杂度，准备动手写代码的时候也想想有没有更好的优化方法，有意识的练习慢慢就会来了感觉。
来自：Python空间（微信号：Devtogether）