一、排序算法

排序也称为排序算法（sort algrithm）,排序是将一组数据，依据指定的顺序进行排序的过程。
**

1、排序的分类

  1. 内部排序：
    • 值将需要处理的所有数据都加载到内部存储器中进行排序。


  1. 外部排序法：
    • 数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。


  1. 常见的排序算法分类

未命名图片.png

二、算法的时间复杂度

1、度量一个程序（算法）执行时间的两种方法：


事后统计法：**

  • 存在的问题：需要实际运行程序，并且每个机器的性能不同，结果就不相同。

  • 这种方式，要在同一个台计算机的相同状态下运行，才能比较哪个算法速度更快。

事前估算法：

  • 通过分析某个算法的时间复杂度来判断哪个算法更优。

2、时间频度

时间频度：一个算法花费的时间与算法中语句的执行次数成正比。哪算法中语句执行次数多，他花费的时间就多。一个算法中的语句执行次数才成为语句频度或者时间频度。 记为T(n)

例如:

  • 使用for循环完成1-100 的求和 T(n) = n + 1;

  • 使用 上底加下底乘高除2 ————-à T(n) = 1

忽略常数项： 例如 3n + 10 和 3n 的差距到最后看都看不，可以把常数（10）去掉

在一个时间复杂度的算式里面 可以忽略常数项

忽略系数项**：例如 5n2+7n 和 3n2+2n 当n越来越大时 表上的曲线即将重合 说明这种情况下下可以忽略3和5

3、时间复杂度

计算时间复杂度的方法（简单的说就是 3n^2+7n+6 取出来 n^2 就行 O(n^2)） n就代表执行多少次

  1. 用常熟项代替运行时间中的所有的加法常数。


  1. 修改后的运行次数函数中，只保留最高阶项。


  1. 去除最高阶项的系数


4、常见的时间复杂度

  1. 常数阶 O(1)
  2. 对数阶 O(log 2n)
  3. 线性阶 O(n)
  4. 线性对数阶 O(nlog 2n)
  5. 平方阶 O(n^2) 双层for循环
  6. 立方阶 O(n^3) 三层for循环
  7. k次方阶O(n^k) k次for循环
  8. 指数阶O(2^n) 尽量避免 太猛了
  9. 阶乘阶 O(n!) 尽量避免 太猛

常见的算法时间复杂度 由小到大依次为 上面的1到8，随着问题规模的n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。我们应该避免使用指数阶和阶乘阶的算法
未命名图片.png

5、详解时间复杂度

5.1 常数阶 O（1）

  1. 无论代码执行了多少行，只要没有循环等复杂结构，那么个代码的时间复杂度就都是O(1)


  1. 他消耗的时候并不是随着某个变量的增长和增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1) 来表示是他的时间复杂度

    5.2 对数阶 O(log 2n)

    1. int i = 1;
    2. int n = 10;
    3. while(i < n){
    4.  i   = i * 2;
    5. }

    5.3 线性阶 O(n) 单层的for循环 \

    1. int n = 100;
    2. int j = 1;
    3. for (int i = 1; i<= n; ++i){
    4.  j   = i;
    5.  j   ++;
    6. }
  • 这段代码，for循环里面的代码会执行n遍，因此它消耗的时间时随着n的变化而变化的，因此这类代码都可以用O(n) 来表示他的时间复杂度


5.4 平方阶 O(n^2)

  • 嵌套一个for循环

5.5 立方阶和K次方阶一致。

5.6 平均时间复杂度和最坏时间复杂度

  1. 平均时间复杂度是指所可能的输入案例均已等概率出现的情况下，该算法运行时间。


  1. 最坏情况下的时间复杂度称为最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。
    • 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长


  1. 平均时间复杂度和最坏时间复杂度是否一致，和算法有关


6、常见算法的时间复杂度

未命名图片.png

三、算法的空间复杂度

1、基本介绍

  1. 类似于时间复杂度的讨论，一个算法的空间复杂度定义为该算法所耗费的存储空间，他也是问题规模n的函数。


  1. 空间复杂度是对一个算法在运行过程中临时占用存储空大小的量度，有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大。当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况


  1. 在做算法分析师，主要讨论的是时间复杂度，从用户使用体验上看，更看重的程序执行的速度。一些缓存产品 (redis,memcache) 和算法（基数排序）本质上就是使用空间换时间