什么是算法

算法(algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列。算法有 5 个特性：

• 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。
• 确定性：对于相同的输人只能得出相同的输出，不能有二义性。
• 可行性：算法中的所有操作都必须足够基本,算法可以通过有限次基本操作来完成其功能。
• 有输人：一个算法有零个或者多个输人。
• 有输出： 一个算法有一个或者多个输出。

算法分析

时间复杂度

算法时间复杂度是以算法中基本操作重复执行的次数作为算法的时间度量。一般不必要精确计算出算法的时间复杂度，只要大致计算出相应的数量级即可，如 O(1)、O(log2n)、O(n)或 O(n2)等。

      T(n)=O(f(n))   f(n)是正整数n(n表示问题的规模)的一个函数。

先来看个简单的例子

//求两个n阶矩阵的乘积算法
for(i=1;i<=n;i++){ //频度为 n+1
 for(j=1;j<=n;j++){ //频度为 n*(n+1)
  c[i][j]=0; //频度为 n^2
  for(k=1;k<=n;k++){ //频度为 n^2*(n+1)
   c[i][j] = c[i][j]+a[i][k]*b[k][j]; //频度为 n^3
  }
 }
}

f(n)=2n^3+3n^2+2n+1

忽略低阶，忽略系数.当 n 无穷大时，f(n)=n^3，3 次方对该方程的影响最大。 所以上面例子时间复杂度：f(n^3)

所以一般情况下:算法中的基本语句的，重复执行的次数，是问题规模 n 的某个函数 f ( n ) f(n)f(n)，算法的时间度量记为：T ( n ) = O ( f ( n ) ) T(n)=O(f(n))T(n)=O(f(n))，他表示问题规模 n 的增大，算法执行时间的增长率和 f(n)的增长率相同，成为算法的渐进时间复杂度，简称为时间复杂度。

for(i=0;i<10000;i++){
 x++;
 s=0;
}
//时间复杂度仍然为O(1)

常见的时间复杂度解析

1.常数阶 O（1）

  int i = 1;
  int j = 2;
  ++i;
  j++;
  int m = i + j;

2.对数阶 O(log2^n)

for(i=1;i<=n;i=i*2){
 x++;
 s=0;
}

可以写出不等式

2^f(n)≤n

f(n)≤log2n

所以时间复杂度： T(n)=O(log2n)

i=1;
while(i<=n)
 i=i*3;

3^f(n)≤n 推出时间复杂度：O(log3n)

3.线性阶 O(n)

for 循环里会执行 n 编,故消耗时间随着 n 的增值而增长故时间复杂度为 O(n)

int n=100;
for(int i = 1;i <= n; i++) {
  int j=i;
  j++;
}

4.线性对数阶 O(Nlog2n)

线性对数阶 O(Nlog22)就是将复杂度为 O(log2n)的代码执行 N 次 就是 N*O(log2n) 为 O（Nlog2n）

int N =1000;
for(int i=0;i<N;++i) {
  while(i<N) {
    i = i * 2;
  }
}

5.平方阶 O(n^2)

套娃 如：两个 for 循环

int n = 100;
for(int i=0;i<n;++i) {
  for(int j=0;j<n;++j) {
    System.out.println("疯狂套娃");
  }
}

常见复杂度递增关系 O(1)<O(log2n)<O(n)<O(nlog2n⟨O(n^2)<O(n^3)<O(2^n)<O(n!)

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。

关于算法存储空间需求，类似于算法的时间复杂度，我们采用渐进空间复杂度作为算法所需存储空间的度量民间称空间复杂度，它也是问题规模 n 的函数

  S(n)=O(f(n))  f(n)是正整数n(n表示问题的规模)的一个函数。

常见的空间复杂度分析

O(1) - 常数空间复杂度：

算法的空间使用与输入规模无关，常数级别的额外空间。

void constantSpaceAlgorithm() {
    int a = 5;  // 常数级别的额外空间
    // 算法逻辑
}

O(n) - 线性空间复杂度：

算法的额外空间随着输入规模线性增长。

void linearSpaceAlgorithm(int arr[], int size) {
    int *tempArray = (int *)malloc(size * sizeof(int));  // 线性级别的额外空间
    // 算法逻辑
    free(tempArray);
}

O(n^2) - 平方空间复杂度：

算法的额外空间随着输入规模的平方增长。

void quadraticSpaceAlgorithm(int n) {
    int **matrix = (int **)malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) {
        matrix[i] = (int *)malloc(n * sizeof(int));  // 平方级别的额外空间
    }
    // 算法逻辑
    for (int i = 0; i < n; i++) {
        free(matrix[i]);
    }
    free(matrix);
}

O(log n) - 对数空间复杂度：

通常出现在递归算法中，递归深度决定了额外空间的增长。

int recursiveFunction(int n) {
    if (n <= 1) {
        return 1;
    }
    return recursiveFunction(n / 2) + recursiveFunction(n / 2);  // 对数级别的额外空间
}