【数据结构】算法的时间复杂度和空间复杂度解析

本文涉及的产品
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 我们在写一个算法的时候如何判断这个算法的好坏呢?我们主要从效率来分析,而效率包括时间效率和空间效率

1. 算法的效率

我们在写一个算法的时候如何判断这个算法的好坏呢?我们主要从效率来分析,而效率包括时间效率和空间效率


时间效率称为时间复杂度,时间复杂度衡量一个算法的运行速度

空间效率称为空间复杂度,空间复杂度衡量一个算法所需要的额外空间


2 时间复杂度

2.1 时间复杂度的概念

在计算机科学中,时间复杂度是一个数学函数,它定量的描述了算法的运行时间,我们把算法中基本的语句执行的次数称为算法的时间复杂度


所谓基本语句在这里指重复执行的语句


2.2 大O渐进表示法

代码基本语句执行次数分析


我们看这样一段代码:

public class Test {
    public void func1(int N){
        int count = 0;
        for(int i = 0;i < N;i++){
            for(int j = 0;j < N;j++){
                count++;
            }
        }
        for(int k = 0;k < 2*N;k++){
            count++;
        }
        int M = 10;
        while((M--) > 10){
            count++;
        }
    }
}


分析一下fun1的基本操作执行了多少次,在fun1中,基本操作也就是count++执行了多少次

微信图片_20221029154440.png

经分析得:fun1执行的基本操作次数为:F(N) = N^2 + 2N + 10

当N=10时,F(N)=130

当N=100时,F(N) = 10210

当N=1000时,F(N) = 1002010


我们从中发现:当N越大时,2N+10对真实的执行次数影响很小,所以实际中我们计算时间复杂度不一定要精确的执行次数,只需要大概的执行次数,所以这里使用大O渐进法表示时间复杂度


大O渐进法


用常数1取代运行次数中所有的加法常数

在修改后的运行次数函数中只保留最高阶项

如果最高阶项存在且不是1,则去掉与这个项相乘的常数

对上述fun1的时间复杂度用大O渐进法表示:


最高阶项为N^2,去掉2N+10

N^2的系数为1,所以不变

故fun1的时间复杂度为:O(N^2)


算法时间复杂度的三种情况


比如在一个数组中查找某个值为n的数:


当数组中第一个元素为我们要查找的数时,1次就找到,为最好情况

当数组中最后一个元素为我们要查找的数时,N次找到,为最坏情况

当数组中中间的元素为我们要查找的数时,N/2次找到,为平均情况

我们实际关注的是算法的最坏情况,以算法的最坏情况作为该算法的时间复杂度,故数组中查找某个数据的时间复杂度为O(N),N为数组的长度


2.3 常见算法的时间复杂度分析

实例1

public void fun2(int N){
        int count = 0;
        for(int k = 0;k < 2*N;k++){
            count++;
        }
        int M = 10;
        while(M > 0){
            count++;
            M--;
        }
    }

 实例2

public void fun3(int N,int M){
        int count = 0;
        for(int i = 0;i < M;i++){
            count++;
        }
        for(int j = 0;j < N;j++){
            count++;
        }
    }

 微信图片_20221029154423.png

实例3

public void fun4(){
        int count = 0;
        for(int i = 0;i < 100;i++){
            count++;
        }
    }

 微信图片_20221029154412.png 

冒泡排序的时间复杂度分析


public void bubbleSort(int[] array){
        for(int i = 0;i < array.length-1;i++){
            for(int j = 0;j < array.length-1-i;j++){
                if(array[j] > array[j+1]){
                    int t = array[j];
                    array[j] = array[j+1];
                    array[j+1] = t;
                }
            }
        }
    }

微信图片_20221029154400.png

二分查找的时间复杂度分析

public int binarySearch(int[] array,int value){
        int begin = 0;
        int end = array.length-1;
        while(begin < end){
            int mid = begin+((end-begin)>>1);
            if(array[mid] < value){
                begin = mid+1;
            }else if(array[mid] > value){
                end = mid-1;
            }else {
                return mid;
            }
        }
        return -1;
    }

  微信图片_20221029154344.png

我们经分析出二分查找的时间复杂度为O(lgN),所以在刷题的时候有些题目对算法要求O(lg2),在没有思路的时候就可以考虑用二分法可不可以解决


阶乘递归的时间复杂度分析

public long factorial(int N){
        return N < 2 ? N : factorial(N-1)*N; 
    }

微信图片_20221029154329.png


斐波那契递归的时间复杂度分析

public long factorial(int N){
        return N < 2 ? N : factorial(N-1) + factorial(N-2);
    }

 微信图片_20221029154314.png

3. 空间复杂度

空间复杂度是对一个算法在运行的过程中对临时占用内存空间大小的一个量度,空间复杂度的核心就是看算法中是否申请了额外空间,计算规则根时间复杂度的计算规则类似,也使用大O渐进表示法


对于递归算法的空间复杂度:单次递归需要的空间 * 递归的深度


3.1 常见空间复杂度分析

实例1

public void bubbleSort(int[] array){
        for(int i = 0;i < array.length-1;i++){
            for(int j = 0;j < array.length-1-i;j++){
                if(array[j] > array[j+1]){
                    int t = array[j];
                    array[j] = array[j+1];
                    array[j+1] = t;
                }
            }
        }
    }

 

发现该冒泡排序没有申请额外的空间,故空间复杂度为O(1)


实例2

ong[] fibonacci(int n) {
        long[] fibArray = new long[n + 1];
        fibArray[0] = 0;
        fibArray[1] = 1;
        for (int i = 2; i <= n ; i++) {
            fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
        }
        return fibArray;
    }

微信图片_20221029154259.png


实例3

public int fun(){
        int[] arr = new int[10];
        arr[0] = 1;
        return arr[0];
    }

微信图片_20221029154240.png

说明:只要申请空间的时候指定了大小,不论多大,空间复杂度为O(1)


实例4

public long factorial(int N){
        return N < 2 ? N : factorial(N-1)*N; 
    }

微信图片_20221029154229.png





相关文章
|
17天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
50 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
12天前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
30 3
|
13天前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
13天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
29 4
|
13天前
|
前端开发 算法 JavaScript
无界SaaS模式深度解析:算力算法、链接力、数据确权制度
私域电商的无界SaaS模式涉及后端开发、前端开发、数据库设计、API接口、区块链技术、支付和身份验证系统等多个技术领域。本文通过简化框架和示例代码,指导如何将核心功能转化为技术实现,涵盖用户管理、企业店铺管理、数据流量管理等关键环节。
|
15天前
|
算法
[数据结构] -- 时间复杂度和空间复杂度
[数据结构] -- 时间复杂度和空间复杂度
12 0
|
7天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
26天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于MSER和HOG特征提取的SVM交通标志检测和识别算法matlab仿真
### 算法简介 1. **算法运行效果图预览**:展示算法效果,完整程序运行后无水印。 2. **算法运行软件版本**:Matlab 2017b。 3. **部分核心程序**:完整版代码包含中文注释及操作步骤视频。 4. **算法理论概述**: - **MSER**:用于检测显著区域,提取图像中稳定区域,适用于光照变化下的交通标志检测。 - **HOG特征提取**:通过计算图像小区域的梯度直方图捕捉局部纹理信息,用于物体检测。 - **SVM**:寻找最大化间隔的超平面以分类样本。 整个算法流程图见下图。
|
4天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。
|
6天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于贝叶斯优化CNN-LSTM网络的数据分类识别算法matlab仿真
本项目展示了基于贝叶斯优化(BO)的CNN-LSTM网络在数据分类中的应用。通过MATLAB 2022a实现,优化前后效果对比明显。核心代码附带中文注释和操作视频,涵盖BO、CNN、LSTM理论,特别是BO优化CNN-LSTM网络的batchsize和学习率,显著提升模型性能。

推荐镜像

更多