常见算法和排序

冒泡排序原理和实现

    1）算法的概念
    2）时间复杂度和空间复杂度的概念    
    3）常见的排序算法和查找算法


时间复杂度和空间复杂度的概念

    算法评定：
       1）算法分析的目的在于选择合适的算法和改进算法
       2）一个算法的评价主要从时间复杂度和空间复杂度来考虑

    时间复杂度：
       执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n的函数f(n),算法的时间复杂度也因此记做T(n) = Of(n)
    问题的规模n越大，算法执行的时间增长率与f(n)的增长率相关，称作渐进时间复杂度

    时间复杂度计算方式
    O(n^2)、O(1)、O(n)、？
    步骤：
       1）得出算法的计算次数的公式
       2）用常数1来取代所有时间中的左右加法常数.
       3）在修改后的运行次数函数中，只保留最高阶项
       4）如果最高阶存在且不是1，则去除与这个项相乘的常数

    
    举例：
    常数阶：O(1)
    线性阶：O(n)
    平(立)方阶：O(n^2) / O(n^3)
    特殊平方阶：O(n^2/2+n/2)->O(n^2)
    对数阶：O(log2n)
    效率：O(1) > O(log2n) > O(n) > O(nlog2n) > O(n^2) > O(n^3) > O(2^n) > O(n!) > O(n^n)


    时间复杂度其他概念
       最坏情况：最坏的情况时的运行时间，一种保证，如果没有特别说明，说的时间复杂度即为最坏情况的时间复杂度。
       平均情况：期望的运行时间

changj
    空间复杂度
       算法需要消耗的内存空间，记做：S(n) = O(f(n))
       包括程序代码所占用的空间，输入数据所有占用的空间和辅助变量所占用的空间这三个方面
       计算和表示方式与时间复杂度类似，一般用复杂度的渐进性来表示。

    空间复杂度的计算方式
       有时用空间来换取时间
       冒泡排序的元素交换，空间复杂度O(1)