【算法 | 概述初识】时间复杂度和空间复杂度(我不信看完这篇文章你还不懂)

目录

🙈什么是算法

🐱算法描述

😺算法与数据结构的联系与区别

😸算法设计的基本步骤

🙈算法分析

🐱算法时间复杂度

😺算法时间复杂度分析

😸递归算法与非递归算法的时间复杂度区别分析

😹二路归并排序递归算法

😻算法空间复杂度

---

🙈什么是算法

算法是求解问题的一系列计算步骤，用来将输入数据转换成输出结果。

如果一个算法对其每一个输入实例，都能输出正确的结果，则称它是正确的。

算法的设计目标：

正确性、可使用性、可读性、健壮性、高效率与低存储量需求。

算法的5个重要特征：

有限性、确定性、可行性、输入性、输出性。

🐱算法描述

例如：1 + 2 + 3 + ... + n。

Java实现：

public class Sum {
    public static int fun(int n, int s){ //形参列表
        if (n<0){
            System.out.println("书写错误");
        }
        s= 0;
        for (int i =1;i<=n;i++){
            s+=i;
        }
        System.out.println(s);
        return s;
    }
    public static void main(String[] args) {
        fun(10,0); // 55
    }
}

JavaScript实现：

😺算法与数据结构的联系与区别

联系：

数据结构是算法设计的基础，算法的操作对象是数据结构。

设计算法通常要构建适合这种算法的数据结构；数据结构设计主要是选择数据的存储方式。

算法设计就是在选定的存储数据上设计一个满足要求的好算法。

区别：

数据结构关注的是数据的逻辑结构、存储结构以及基本操作，算法更关注如何在数据结构的基础上解决实际问题。

算法是编程思想，数据结构则是这些思想的逻辑基础。

😸算法设计的基本步骤

🙈算法分析

算法分析是分析算法占用计算机资源的情况。所有算法分析的两个主要方面是分析算法的 时间复杂度 和 空间复杂度 。

🐱算法时间复杂度

算法的时间复杂度是一个函数，它定性描述该算法的运行时间，这是一个代表算法输入值的字符串的长度函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考查输入值大小趋近无穷时的情况。

以下面的Java和JavaScript举例:

当电脑运行以上代码时，执行任何一条语句都需要花费时间。根据上图代码，很容易看出红色执行的是 1 个时间单元；绿色执行的是 n + 1 个单元； 蓝色执行的是 n 个时间单元。

红框两条语句，花费 2 个时间单元

绿框一条语句，花费 n + 1 个时间单元

蓝框两条语句，花费 2*n 个时间单元

可以看出代码一共花费了 3n + 3 个时间单元，程序运行可以用 T(n) = 3n + 3 来线性表示。

根据上例引入如下概念：

设 n 为算法中的问题规模，通常用大O、大Ω和Θ等三种渐近符号表示算法的执行时间与n之间的一种增长关系。

渐近符号（O、Ω和Θ）：

O符号：

f(n) = O(g(n))（“f(n)是g(n)的大O”）当且仅当存在正常量c和k，使n>=k时，f(n) <= cg(n)，即g(n)为f(n)的渐近的上界。

说白了就像是高等数学里面的数值无穷大时，就会忽略系数和常数项。以下举例说明：

3n + 2 = O(n)                                10n^2 + 4n + 2 = O(n^2)

当n无穷大时，就取次数项最高的数。

o符号：

f(n) = o(g(n))：对于任意正常量 c 都存在 k，使当 n >= k 时，f(n) < c(g(n))。

Ω符号：

f(n) = Ω(g(n))（“f(n)是g(n)的大Ω”）当且仅当存在正常量 c和k时，使当 n>= k 时，f(n) >= cg(n)，即g(n)为f(n)的渐近的下界。

3n + 2 = Ω(n)                                10n^2 + 4n + 2 = Ω(n^2)

当n无穷大时，就取次数项最高的数。

ω符号：

f(n) = ω(g(n))：对于任意正常量c均存在 k ，使当 n >= k 时，f(n) > cg(n)。

Θ符号：

f(n) = Θ(g(n))（读作“f(n)是g(n)的大Θ”）当且仅当存在正常量 c1、c2和k，使当 n >= k，有c1g(n) <= f(n) <=c2g(n)，即g(n) 与 f(n) 同阶。

3n + 2 = Θ(n)                                10n^2 + 4n + 2 = Θ(n^2)

当n无穷大时，就取次数项最高的数。

根据上文对三种符号的讲解，我们很容易得到如下概念：(会点高数很容易看懂！)

T(n)=n+1 忽略常数项 T(n)~n

T(n)=n+n^2 忽略低阶项 T(n)~n^2

T(n)=3n 忽略最高阶的系数 T(n)~n

时间复杂度具体到数学知识就不再讲解，我们只需要记住如下大小关系：

O(1) < O(log n) < O(n) < O(nlog n) < O() < O() < O() < O(n!) < O()

😺算法时间复杂度分析

Java实现：

public class Sum {
    public static void main(String[] args) {
        int sum = 0;
        int n = 10;
        for(int i=0;i<=n;i++){
            for(int j=0;j<=i;j++){
                for(int k=0;k
                    sum++;
                }
            }
        }
        System.out.println(sum); //220
    }
}

JavaScript实现：

这个算法的三层循环原理很简单，看如下图解：（时间复杂度为：O() ）

算法的最好、最坏和平均情况：

设一个算法的输入规模为n，是所有输入的集合，任一输入 I ∈，P(I)是I出现的概率，有∑P(I) = 1,T(I)是算法在输入I下所执行的基本语句次数，则该算法的平均执行时间为:A(n)=∑P(I)*T(I)。

算法的最好情况为：G(n) = MIN{T(I)}，是指算法在所有输入I下所执行基本语句的最少次数

算法的最坏情况为：G(n) = MAX{T{I}}，是指算法在所有输入I下所执行基本语句的最大次数

😸递归算法与非递归算法的时间复杂度区别分析

递归算法的时间复杂度分析：

递归算法是采用一种分而治之的方法，把一个“大问题”分解为若干个“小问题”来求解。

对递归算法时间复杂度的分析，关键是根据递归过程建立递归关系，然后求解这个递推关系式，得到一个表示算法执行时间的表达式，最后用渐进符号来表示这个表达式即得到算法的时间复杂度。

非递归算法的时间复杂度分析：

对于非递归算法，分析其时间复杂度相对比较简单，关键是求出代表算法执行时间的表达式。

通常是算法中基本语句的执行次数，是一个关于问题规模n的表达式，然后用渐近符号来表示这个表达式即得到算法的时间复杂度。

😹二路归并排序递归算法

将已有序的的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将俩个有序表合并成一个有序表，称为二路合并。进行有序合并时间复杂度为：O(n)。

Java实现：

import java.util.Arrays;
public class Sum {
    public static void main(String[] args) {
        int []a={4,9,2,7,1,8,9,5,3};
        mergeSort(a, 0, a.length-1);
        System.out.println(Arrays.toString(a));
 
    }
    public static void mergeSort(int[]a,int low,int high ){
        if(low//递归结束条件
            int mid=(low+high)/2;
            mergeSort(a, low, mid);//左子表递归排列有序
            mergeSort(a,mid+1,high);//右子表递归排列有序
            merge(a,low,mid,high);//将两有序子表合并
        }
 
    }
    public static void merge(int []a,int low,int mid,int high){//两有序子表合并方法
 
        int [] temp=new int[9];//这里把要排序数组copy一份，用来比较，原来的数组用来保存比较后的信息
        for(int i=low;i<=high;i++){//注意这里copy时，下标是从low开始的，要是为了保证copy的数组下标与目标数组下标一致，这样是为了方便后面的比较的下标操作
            temp[i]=a[i];//当然copy的数组保存时也可以从0开始保存，但是这样就要注意后面的比较操作时，i就不是小于mid了，而是小于mid-low，j也不是小于high，j是小于high-low
 
        }
        int i=low,j=mid+1,k=low;//把数组分为前后相同的两端进行比较。i指向前半段，j指向后半段，k指向要保存的位置
        for(;i<=mid&&j<=high;k++){//比较
            if(temp[i]
            else a[k]=temp[j++];
 
        }
        while(j<=high)//若第一个表没检测完，复制
            a[k++]=temp[j++];
 
        while(i<=mid)//若第二个表没检测完，复制
            a[k++]=temp[i++];
    }
}

JavaScript实现：

😻算法空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。算法的空间复杂度S(n)定义为该算法所消耗的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。

一个算法的存储量包括形参所占用空间和临时变量所占空间。在对算法进行存储空间分析时，只考虑临时变量所占空间。

讲解空间复杂度的相关案例情况：

//常量空间:当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记作O(1)。
var m = 1;
 
//线性空间:当算法分配的空间是一个线性的集合（如数组），并且集合大小和输入规模 n 成正比时，空间复杂度记作 O(n)。
var newArr = new Array()
 
//二维空间:当算法分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模 n 成正比时，空间复杂度记作 O( n 2 n^2 n2)。
//JS中没有二位数组的概念，我们这里就借用Java
int[][] matrix = new int[n][n];
 
//类似时间复杂度，如果为 int[][] matrix = new int[m][n]; 的话，复杂度就是 O(mn) 了。

而我们在使用递归的时候，执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是 O(n)。如下图：

正如上述代码一样，递归代码中没有显示声明变量或者集合，但是计算机在执行程序时，会专门分配一块内存，用来存储“方法调用栈”。方法调用栈包括入栈和出栈两个操作：

当进入一个新方法时，执行入栈操作，把调用的方法和参数信息压入栈中。

当方法返回时，执行出栈操作，把调用的方法和参数信息从栈中弹出。

以C为例的图片讲解如下：(返回的结果仍然只是一个数)