前言
今天我们来讨论一下之前总结哒算法的复杂程度。。就是时间和空间复杂程度啦~
什么是时间和空间复杂程度呢？
首先是时间复杂程度。
在讨论时间复杂程度之前，先解释时间频度：一个算法执行所花费的时间，理论上只能测才可以测出来的。一个算法所花费的时间与语句的执行次数成正比。那个算法语句执行次数多，它花费的时间就多。一个算法的语句执行次数成为语句的频度，或时间频度。记为T（n）。
T（n）中哒n是问题的规模，当n不断变化时，T（n）也会不断的变化。但是是什么规律呢？一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数。如果有某个辅助函数f(n)，是的当n为无穷大时， T(n)/f(n)为一个不等于0的常数，则f(n)是T（n）的同数量级函数，记作T（n） = O（f（n）)，我们称O(f(n))为算法的渐进时间复杂度。即时间复杂程度。
在算法中，如果语句执行次数是一个常数，则时间复杂程度为O(1)。另外，在频度不同的情况下，时间复杂程度有可能相同，比如 T(n)=n2+3n+4与T(n)=4n2+2n+1，他们的时间复杂程度都是O（n^2)。明白了吧。。T（n）的最大阶数使我们的时间复杂程度。
然年后是空间复杂程度：
空间复杂程度和时间复杂程度类似，空间复杂程度是指算法在计算机内执行所需要存储空间的度量。记作S(n) = O(f(n))。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为0(10g2n)；当一个算法的空I司复杂度与n成线性比例关系时，可表示为0(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。
冒泡排序
冒泡的时间复杂程度是O（n^2）。很好理解，每次插一个到有序组中，插入时比较的次数是n阶，把所有的元素提取出来拿来插入，也是n阶，所以相乘就是n的平方啦~。
空间复杂程度O（1）。我们并不需要开辟额外空间。
选择排序
选择排序，当然之前写的开辟了新的数组。。其实不用。。
我们每次从无序组找出最大的放到数组最后。每次操作的次数是n阶，（n -1,n-2,….. )。所以时间复杂程度是n乘以n, O（n^2）.
选择排序其实也不需要开辟新的空间（当然我这样做了= =）
插入排序
插入排序每次从无序组中取一个出来，插入到有序组中。二者都是n阶（都是1 ~ n相乘，n阶）所以也是O（2）。
插入排序同样没有开辟新的空间。。（虽然我第一种写法开辟了。。）
快速排序
快排就不一样了。如果我们的Pivot一直取中间那么，我们操作的次数就会大大减少。并且是以2的对数阶减少。在进行分组的过程中，我们的操作次数是总规模的log n 。而在进行左右排布时，操作次数是n阶。故O（nlongn).最差O（n^2 )
归并排序
归并排序主要操作在于合并数组和将数组分割。分割操作使得规模以对数减少，而数组合并操作的阶数是N.so 相乘以后是 O(n * log n).
希尔排序
希尔排序是直插的优化版本，排序时使用gap将数组进行分组。然后对分组内容来直插。他的时间复杂程度很纠结。。据说是nlogn,也有说是n^1.3..目前还是个未解之谜。。
空间复杂度当然是O（1）啦
堆排序
太复杂了。。贴一下证明。。
推算过程：
首先要理解怎么计算这个堆化过程所消耗的时间，可以直接画图去理解；
假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；
那么总的时间计算为：s = 2^( i - 1 ) ( k - i )；其中 i 表示第几层，2^( i - 1) 表示该层上有多少个元素，( k - i) 表示子树上要比较的次数，如果在最差的条件下，就是比较次数后还要交换；因为这个是常数，所以提出来后可以忽略；
S = 2^(k-2) 1 + 2^(k-3)2…..+2(k-2)+2^(0)*(k-1) ===> 因为叶子层不用交换，所以i从 k-1 开始到 1；
这个等式求解，我想高中已经会了：等式左右乘上2，然后和原来的等式相减，就变成了：
S = 2^(k - 1) + 2^(k - 2) + 2^(k - 3) ….. + 2 - (k-1)
除最后一项外，就是一个等比数列了，直接用求和公式：S = { a1[ 1- (q^n) ] } / (1-q)；
S = 2^k -k -1；又因为k为完全二叉树的深度，所以 (2^k) <= n < (2^k -1 )，总之可以认为：k = logn （实际计算得到应该是 log(n+1) < k <= logn ）;
综上所述得到：S = n - longn -1，所以时间复杂度为：O(n)
更改堆元素后重建堆时间：O(nlogn)
推算过程：
1、循环 n -1 次，每次都是从根节点往下循环查找，所以每一次时间是 logn，总时间：logn(n-1) = nlogn - logn ；
桶排序
时间复杂程度O（n )。 = = 演算嘛
http://cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-assignments/Bucket-Sorting-Expected-Complexity.pdf
计数排序
计数排序是非比较排序。很容易看粗来，他的时间复杂程度是O（n)，但是空间复杂程度就。。。是O(m)，m跟最大数值有关啦。
基数排序
时间复杂程度 O( d(n+r) ) d是位数 r是基数
结语
其实google这么久。发现如果真的要对算法的复杂程度进行计算，其实挺麻烦的。。
不过了解一下这些东西，还是有不少好处哒。。（希望自己能真正进入编程之路Orz)