算法

复杂度分析

数据结构和算法本身解决的是“快”和“省”的问题，即如何让代码运行的更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标。那么如何来考量呢？

答案就是：时间、空间复杂度分析。掌握了时间、空间复杂度分析，就能更好地应用数据结构和算法。

大O表示法

算法的执行效率，粗略地讲，就是算法代码执行的时间。就是在不运行代码的情况下，用 “肉眼” 来观察到代码的大约执行时间。

比如下面代码：

int sum = 0;
for(int i=0;i<n;i++){
    sum += i;
}
System.out.println(sum);

第一行执行1次，第二行开始到第四行是一个循环，循环了n次，第五行执行了一次，假设每行代码执行的时间都一样，为unit_time，那么整段代码执行时间为：(n+2)*unit_time 次，所有代码的执行时间T(n) 与每行代码的执行次数成正比。

按这个思路分析，尽管我们不知道unit_time的具体值，但通过这段代码执行时间的推导过程，可以得到一个非常重要的桂林，就是所有代码的执行时间T(n)与每行代码的执行次数n成正比。我们可以把这个规律总结一个公式，就是：

这就是大O表示法，即 “大约” 表示法。

时间复杂度

因为不是非常精确的，但是所表达的是代码执行时间随数据规模增长的变化趋势，所以也叫渐进时间复杂度。

常见复杂度量级主要分为2大类，**多项式量级 **和 非多项式量级。如图：

O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。

O(logn)、O(nlogn) 对数阶时间复杂度，归并排序、快速排序的时间复杂度都是 O(nlogn)

按复杂度量级排序，从低阶到高阶有，O(1)、O(logn)、O(n)、O(nlogn) ....：

空间复杂度

算法占用空间大小称为空间复杂度。对于好的算法评判标准就是高效率、低存储。

比如排序算法中的，计数排序就用了额外的空间，而归并排序、插入排序等算法就没有用额外的空间存储。

作者： Zealon
崇尚简单，一切简单自然的事物都是美好的。