算法简介

算法是为了解决某一特定问题而规定的一系列操作，是一组有序、有限的指令集合。
算法有以下五个特征：
有穷性：一个算法必须总是在执行有穷步之后结束，并且每一步都可在有限时间内完成。
确定性：算法种的指令必须有确切的意义，即对于特定的合法输入其输出结果是确定的。
可行性：计算机能够执行算法，并在有限时间内执行完成。
输入：一个算法必须有一个或多个输入。
输出：一个算法必须有一个或多个输出。

时间复杂度

讨论程序运行的时间有事后统计和事前分析两种方式，事后统计是计算实现算法需要的时间，但不同配置的计算机执行同一算法时间上是会有差异的，所以一般采用事前分析的方式来衡量算法的时间复杂度，即分析语句执行的次数的规模。

  1. package package01;
  3. /**
  4.  * @author wjh
  5.  * @date 2021/7/10 10:53
  6.  * @Package package01
  7.  */
  8. public class Test01 {
  9.     public static void main(String[] args) {
  10.         int n = 100;
  11.         for (int i = 0; i < n; i++) {
  12.             System.out.println("test" + i);
  13.         }
  14.     }
  16. }

分析：int n=0和int i=0;各执行一次；i<n执行n+1次；i++和sout语句各执行n次，所有这个方法总执行次数是2+(n+1)+2n=3(n+1)，为了方便讨论，这里我们把每一条语句的执行时间都看做是一样的，记为一个时间单元，可以一共需要T(n)=3(n+1)个时间单元，程序运行时间和n是线性关系。但是我们只关心随着问题规模n趋于无穷时函数中对函数结果影响最大的项，即最高次项，并且会忽略前面的系数，因此这段程序的时间复杂度可以表示为T(n)=O(n)。

时间复杂度的一般计算方法：
得出运行时间的函数->用常数1来取代运行时间中所有加法常数->修改后的函数中，只保留最高阶项->如果最高阶项存在且不是1，则忽略这个项的系数
看一些例子：
image.png
一般来说，最内层执行次数最多的语句决定了整个算法的趋势
image.png
image.png
常见时间复杂度大小关系：
算法与算法分析 - 图4

参考文章：https://blog.csdn.net/m0_37907797/article/details/116157862

空间复杂度

空间复杂度用的不多，暂时简单介绍：
image.png