1、算法

  • 算法就是为了解决某一特定问题而规定的一系列操作，是一组有序的指令的集合。
  • 算法和数据结构往往需要放在一起分析

  • 算法的使用会使代码更加简介，程序更加快速（正确使用的情况下），例如求和1~10000，使用for循环和算法

    1. private static void doSum(int num){
    2.   int sum = 0;
    3.   for (int i = 0; i <= num; i ++){
    4.       sum += i;
    5.   }    
    6.    System.out.println(sum);
    7. }
    8. private static void doSum1(int num){
    9.   int sum = (1+num)*num/2;
    10.   System.out.println(sum);
    11. }

    1.1、算法的特性

  • 输入：一个算法有0个或多个输入

  • 输出：至少有一个输出
  • 有穷性：算法中执行指令的个数应该是有限的，执行有穷的步骤后能结束
  • 确定性：对于特定的合法输入，输出应该是唯一的

  • 可行性：算法能够实现，并且在有限的时间内完成

    1.2、算法的设计要求

  • 正确性：没有语法错误，对于合法是输入可以产生满足要求的输出，对于特定的输入也能够产生正确的输出

  • 可读性：算法的另一个目的是为了交流，方便交流
  • 健壮性：对于不合理的输入，也可以给出合理的提示信息，而不是程序崩溃
  • 时间效率与存储空间：时间效率高、存储空间小

  • 评价一个算法性能的好坏，实际上就是评价的资源占用率，计算机重要的资源就是时间和空间

    • 使用时间复杂度来衡量程序运行占用的时间
    • 使用空间复杂度来衡量程序运行占用的空间

      2、算法的时间复杂度

  • 使用时间复杂度来衡量程序运行占用的时间

  • 讨论计算机程序的运行时间可以采用以下的方法：

    • 事后统计：编程实现算法，多次运行，统计运行所需的时间，但是硬件环境这种方式对于方式影响较大
    • 事前分析：采用渐进时间复杂度分析估算
      • 在进行算法分析的时候，语句总的执行次数（记作T(n)），是关于问题规模n的函数
      • 分析T(n)对着问题规模n的变化情况，确定T(n)的数量级
      • T(n)=O(f(n))，表示随着问题规模n的扩大，算法执行时间的增长率和f(n)函数的增长率相同，f(n)是问题规模n的一个函数
        • 随着输入规模n的增大，T(n)增长越慢的算法越好

          3、算法时间复杂度分析

  • 算法1：高斯算法计算1+2+3+…+num的和

    1. private static void doSum1(int num){
    2.   int sum = (1+num)*num/2;
    3.   System.out.println(sum);
    4. }
    • 顺序执行，时间复杂度：T(n)=O(1)，是常数阶

  • 算法2：使用for循环计算1+2+3+…+num的和

    1. private static void doSum2(int num){
    2.   int sum = 0;
    3.   for (int i = 0; i <= num; i ++){
    4.       sum += i;
    5.   }    
    6.    System.out.println(sum);
    7. }
    • T(n)=O(n)，线性阶

  • 算法3：

    1. private static void method(int num){
    2.   int i = 1;
    3.   int count = 0;
    4.   while (i <= num){
    5.       i = i *2;
    6.       count++;
    7.   }
    8.   System.out.println(count);
    9. }
    • 循环控制变量 i 的值：1，2，4，8，…，2，当执行了n次，i 的值为 2 时，循环结束，循环条件为i <= num，所以2>= num的时候循环结束
    • 所以，T(n)=O(logn)

  • 算法4：

    1. private static void method2(int num){
    2.   int count = 0;
    3.   int i = 0;
    4.   while(i <= num){
    5.       i = i + count;
    6.       count ++;
    7.   }
    8.   System.out.println(count);
    9. }

    | count | 0 | 1 | 2 | 3 | 4 | 5 | … | x | | —- | —- | —- | —- | —- | —- | —- | —- | —- | | i | 0 | 1 | 3 | 6 | 10 | 15 | … | (0+1+2+…+x)=(1+x)*x/2=(x2+x)/2 |

    • 循环控制条件false的时候，(x2+x)/2>=num的时候退出循环，当num足够大的时候T(n)=O(n2)

  • 算法5：

    1. private static void method3(int num){
    2.   int count = 0;
    3.   for (int i = 1; i <=num; i++){
    4.       for (int j = 1; j <= num; j ++){
    5.           count ++;
    6.       }
    7.   }
    8.   System.out.println(count);
    9. }

    | n | 1 | 2 | 3 | 4 | 5 | 6 | … | n | | —- | —- | —- | —- | —- | —- | —- | —- | —- | | count | 1 | 2 | 9 | 16 | 25 | 36 | … | n |

    • 最后count++执行的次数是n次数，所以T(n)=O(n)
  • 常见的时间复杂度增长率：

image.png

4、算法的空间复杂度

  • 使用空间复杂度来衡量程序运行占用的空间
  • 为了求解某一问题，在执行操作期间所需要的存储空间大小，一般不包含存储输入所需要的空间
  • 记作：S(n)=O(f(n))
  • 结论：算法的空间复杂度为上限的，所以大多数情况下我们只考虑时间复杂度