Java时间复杂度和空间复杂度(详解)

目录

1.复杂度分析

2.时间复杂度

大O的渐进表示法

3.空间复杂度


1.复杂度分析

当我们设计一个算法时,怎样衡量其好坏?

算法在编写为可执行程序后,运行时需要耗费时间资源和空间(内存)资源。因此,衡量一个算法的好坏,一般是从时间空间两个方面来衡量。

2.时间复杂度

一个算法执行所需要的时间,我们可以将代码跑一遍得到具体的时间,但是如果每一个算法都测试一遍的话,十分耗费时间和精力,而且,其测试的结果高度依赖于测试环境,测试环境中的硬件不同会影响测试结果,测试数据的规模也会影响测试结果。

如果我们假设每行代码执行的时间都相同,那么此时影响时间的因素为语句的执行次数,即时间与其语句的执行次数成正比例

时间复杂度:算法中的基本操作的执行次数

public static int factorial(int N){int ret = 1;for (int i = 2; i <= N; i++) {ret *= i;}return ret;}

上述代码用来求n的阶乘,其中,在for前的代码每行执行了一次,在for循环(i++)及其中的代码(ret *= i)每行执行了N-1次,那么该代码总执行了(1+2*(N-1))次,即(2*N-1)次,代码具体执行了多少次,与传入数据n相关。

当 N = 100 时,代码执行 199 次

当 N = 1000时,代码执行 1999次

当 N = 10000时,代码执行 19999次

……

N越大,常数 -1,系数2对执行次数的影响越小。

因此,我们在计算时间复杂度时,并不需要计算精确的执行次数,只需要计算出其大概执行的次数,我们用大O的渐进表示法来表示

大O的渐进表示法

大O符号(Big O notation):用于描述函数渐进行为的数学符号

推导大O阶方法:

1.用常数1取代运行时间中所有的加法常数

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

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

例如,上述求阶乘的代码中,其执行次数为 2*N-1,用大O的渐进表示法,去掉对结果影响不大的项 -1,最高阶项去除与其相乘的常数,即为O(N)

在算法中,存在不同的执行情况,

例如在长度为N的数组中查找数据x时,可能执行一次就找到,也可能执行n次也找不到

我们将其分为最好、平均和最坏情况

最好情况:任意输入规模的最小运行次数

平均情况:任意输入规模的期望运行次数

最坏情况:任意输入规模的最大运行次数

而我们一般关注的是算法的最坏运行情况

我们通过一些例子来进一步熟悉大O的渐进表示法:

由于我们需要去掉对结果影响不大的项,因此我们可以不再分析对结果影响较小的语句。

例1:

public static int add(int a, int b){int ret = a+b;return ret;}

上述代码一共执行两次,用常数1取代其中的常数,即为 O(1)

例2:

 int fun(int N,int M){int count = 0;for (int i = 0; i < N; i++) {count++;}for (int i = 0; i < M; i++) {count++;}return count;}

上述代码一共有两个for循环,其中对执行次数影响最大(即执行次数最多)的语句为count++,共共执行了 N+M 次,

当 N 远大于 M时,时间复杂度为 O(N)

当 M 远大于 N时,时间复杂度为 O(M)

当 M 与 N 差不多大时,时间复杂度为 O(M+N)

由于没有说明N与M的大小关系,时间复杂度为 O(N+M)

例3:

    void fun(int N){int count = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < i; j++) {count += j;}}}

 上述代码中有一个嵌套循环,其中对执行次数影响最大的语句为 count += j,我们对其进行分析

当 i = 0 时,语句执行 0 次,

当 i = 1 时,语句执行 1 次,

当 i = 2 时,语句执行 2 次,

……

当 i = N-1时,语句执行 N-1次

则总执行次数为 0 + 1 + 2 + …… + N-1,利用等差数列求和公式,可得结果为\frac{(N-1)*N}{2},最高阶项为\frac{^{N{_{}}^{2}}}{2},去掉系数,时间复杂度为 O(N^2)

例4:

void fun(int M){int count = 0;for (int i = 0; i < 10; i++) {count++;}}

 时间复杂度为O(1)

注意!count++ 语句一共执行了10次,与M没有关系

例5:

  public static int binarySearch(int[] arr, int x){if(arr.length == 0){return -1;}int left = 0;int right = arr.length-1;while(left <= right){int mid = left + ((right-left)>>1);if(arr[mid] == x){return mid;}else if(arr[mid] > x){right = mid;}else{left = mid+1;}}return -1;}

上述代码为二分查找,考虑最坏的情况,即查找不到:

我们先分析二分查找是如何查找数据的:

二分查找的前提是被查找的数组arr有序,通过确定中间位置mid,将数组分为两个部分,若被查找值x < arr[mid],则排除右边部分值,在左边继续进行二分查找;若x > arr[mid],则排除左边部分值,在右边继续进行二分查找;若 x = arr[mid],则找到被查找值,返回即可。

过程如下图所示:

由于一次二分查找会排除数组一半的元素,即

N/2

N/4

N/8

……

1 当结果为1时循环结束

因此 1*2*2*……*2 = N,即 2^x = N,则执行次数x = {log_{2}}^{}N

时间复杂度为O(log_{2}^{}N)

例6:

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

 上述递归的结束条件为 N < 2,当N >= 2时,会一直递归下去:

N

N-1

N-2

……

2

1 此时递归结束

递归的次数为N,因此时间复杂度为O(N)

例7:

    int fibonacci(int N){return N < 2? N: fibonacci(N-1)+ fibonacci(N-2);}

斐波那契递归,可将其看成一个二叉树,将其递归时开辟的栈帧看作一个节点,每一个节点就是一次函数调用,则递归的时间复杂度为二叉树结点个数,具体递归过程为:

 

其中最后一层可能不满,由于计算时间复杂度只需要计算出其大概执行的次数,最后一层的空缺对计算的影响可以忽略不计

则递归的次数为Fib(N) = 2^0 + 2^1 + ……+ 2^(N-1) 

 利用等比数列求和公式,可得2^n - 1,则时间复杂度为O(2^N)

3.空间复杂度

空间复杂度是对一共算法在运行过程中临时占用存储空间大小的量度。空间复杂度计算的是变量的个数,其计算规则基本与时间复杂度类似,也使用大O的渐进表示法

例1:

    void fun(int N){int count = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < i; j++) {count += j;}}}

 其中开辟了常数个额外的变量(count、i、j),因此空间复杂度为O(1)

例2:

    int[] fun(int N){int[] arr = new int[N];for (int i = 0; i < N; i++) {arr[i] = i;}return arr;}

 开辟了一共大小为N的整形数组和常数个额外的变量,因此空间复杂度为O(N)

例3:

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

上述代码递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间,因此空间复杂度为O(N)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/132161.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

使用新版Maven-mvnd快速构建项目

目前我们项目的构建方式多数是 maven、gradle&#xff0c;但是 maven 相对 gradle 来说&#xff0c;构建速度较慢&#xff0c;特别是模块相对较多的时候&#xff0c;构建速度更加明显。但是我们将项目由 maven 替换为 gradle 相对来说会比较麻烦&#xff0c;成本较高。于是我们…

Qt的ui文件不能简单复制

在使用vsQt开发时&#xff0c;直接复制另外一个widget类的ui文件&#xff0c;简单改名成当前类对应的ui文件&#xff0c;会导致编译出错。尽可能使用添加的Qt class自带的ui文件&#xff0c;因为ui文件的配置文件中有许多与当前类相关的字符串&#xff0c;简单复制容易报错。

二刷力扣--字符串

字符串 摘自Python文档-标准库&#xff1a; 在Python中&#xff0c; 字符串是由 Unicode 码位构成的不可变序列。 由于不存在单独的“字符”类型&#xff0c;对字符串做索引操作将产生一个长度为 1 的字符串。 也就是说&#xff0c;对于一个非空字符串 s, s[0] s[0:1]。 不存…

分布式调度 Elastic-job

分布式调度 Elastic-job 1.概述 1.1什么是任务调度 我们可以思考一下下面业务场景的解决方案: 某电商平台需要每天上午10点&#xff0c;下午3点&#xff0c;晚上8点发放一批优惠券某银行系统需要在信用卡到期还款日的前三天进行短信提醒某财务系统需要在每天凌晨0:10分结算…

IP地址SSL证书的作用是什么?

IP地址SSL证书的作用是确保网站连接的安全性和可信度。具体而言&#xff0c;IP地址SSL证书的作用包括以下几个方面&#xff1a; 1. 数据加密&#xff1a;IP地址SSL证书使用SSL协议为网站提供了数据加密功能。通过加密传输&#xff0c;证书可以保护敏感信息&#xff08;如用户登…

每日刷题-5

目录 一、选择题 二、算法题 1、不要二 2、把字符串转换成整数 一、选择题 1、 解析&#xff1a;printf(格式化串&#xff0c;参数1&#xff0c;参数2,.….)&#xff0c;格式化串: printf第一个参数之后的参数要按照什么格式打印&#xff0c;比如%d--->按照整形方式打印&am…

《TCP/IP网络编程》阅读笔记--Timewait状态和Nagle算法

1--Timewait状态 对于服务器端/客户端&#xff0c;当一端结束连接时&#xff0c;会向另一端发送 FIN 消息&#xff1b;两端的在经过四次挥手过程后&#xff0c;其 Socket 不会马上消除&#xff0c;而是会处于一个 Time-wait 状态的阶段&#xff0c;此时 Socket 拥有的端口号并没…

c语言练习57:浮点数在内存中的存储

浮点数在内存中的存储 上⾯的代码中&#xff0c; num 和 *pFloat 在内存中明明是同⼀个数&#xff0c;为什么浮点数和整数的解读结果会差别 这么⼤&#xff1f; 要理解这个结果&#xff0c;⼀定要搞懂浮点数在计算机内部的表⽰⽅法。 根据国际标准IEEE&#xff08;电⽓和电⼦⼯…

Linux服务使用宝塔面板搭建网站,并发布公网访问

文章目录 前言1. 环境安装2. 安装cpolar内网穿透3. 内网穿透4. 固定http地址5. 配置二级子域名6. 创建一个测试页面 前言 宝塔面板作为简单好用的服务器运维管理面板&#xff0c;它支持Linux/Windows系统&#xff0c;我们可用它来一键配置LAMP/LNMP环境、网站、数据库、FTP等&…

“山东工行杯”山东省第五届数据应用创新创业大赛开赛!

由山东省大数据局、共青团山东省委、山东省教育厅、山东省科学技术厅联合主办的“山东工行杯”山东省第五届数据应用创新创业大赛已于8月30日正式启动报名&#xff01;本届大赛以“场景赋能&#xff0c;数创齐鲁”为主题&#xff0c;设置数据赋能经济发展、数据赋能公共服务、数…

服务器数据恢复-Xen server虚拟机数据恢复案例

服务器数据恢复环境&#xff1a; 一台某品牌服务器通过一张同品牌某型号RAID卡将4块STAT硬盘组建为一组RAID10阵列。上层部署Xen Server虚拟化平台&#xff0c;虚拟机上安装的是Windows Server操作系统&#xff0c;包括系统盘 数据盘两个虚拟机磁盘&#xff0c;作为Web服务器使…

快速导入mysql较大的SQL文件

一般情况下&#xff0c;我们的网站或者小项目的数据库文件也就几十兆的大小&#xff0c;使用navicat等可视化工具快速就可以导入成功&#xff0c;但是当我们遇到几百兆或者更大的数据库文件时候&#xff0c;使用这些可视化工具去操作肯定是不可以的&#xff0c;亲测导入时间会特…

Pod和容器设计模式

为什么需要Pod 一些应用的实现是需要多个进程配合完成的&#xff0c;由于容器实际上是一个“单进程”模型&#xff0c;如果在容器里启动多个进程会存在进程管理的难题。在Kubernetes里面&#xff0c;实际上会被定义为一个拥有四个容器的Pod。 Pod相当于进程组 Kubernetes 是…

CSS文字居中对齐学习

CSS使用text-align属性设置文字对齐方式&#xff1b;text-align:center&#xff0c;这样就设置了文字居中对齐&#xff1b; <!DOCTYPE html> <html><head><meta charset"UTF-8"><title>css 水平居中</title><style>.box …

【SpringBoot集成Redis + Session持久化存储到Redis】

目录 SpringBoot集成Redis 1.添加 redis 依赖 2.配置 redis 3.手动操作 redis Session持久化存储到Redis 1.添加依赖 2.修改redis配置 3.存储和读取String类型的代码 4.存储和读取对象类型的代码 5.序列化细节 SpringBoot集成Redis 1.添加 redis 依赖 …

Redis从入门到精通(二:数据类型)

数据存储类型介绍 Redis 数据类型&#xff08;5种常用&#xff09; string hash list set sorted_set/zset&#xff08;应用性较低&#xff09; redis 数据存储格式 redis 自身是一个 Map&#xff0c;其中所有的数据都是采用 key : value 的形式存储 数据类型指的是存储的数据…

关于接口自动化,你不能不知道的高级技巧——接口自动化神器apin进阶操作

一、变量提取和引用 变量提取和引用主要是为了解决接口之间的参数依赖问题。 使用场景&#xff1a;接口 A 的参数中需要使用接口 B 返回的某个数据&#xff0c;那么就要在请求 B 接口之后&#xff0c;提取数据保存&#xff0c;给请求 A 接口时使用。 1、变量提取 在用例集或…

【开发】视频集中存储/直播点播平台EasyDSS点播文件分类功能优化

视频推拉流EasyDSS视频直播点播平台&#xff0c;集视频直播、点播、转码、管理、录像、检索、时移回看等功能于一体&#xff0c;可提供音视频采集、视频推拉流、播放H.265编码视频、存储、分发等视频能力服务。 TSINGSEE青犀视频的EasyDSS平台具有点播文件分类展示方法&#xf…

【智慧工地源码】物联网和传感器技术在智慧工地的应用

物联网&#xff08;IoT&#xff09;和传感器技术在智慧工地中扮演着至关重要的角色。这些技术的应用&#xff0c;使得智慧工地能够实现对施工过程的精确监控、数据收集和分析&#xff0c;以及设备互联&#xff0c;从而提高工程效率、减少成本并改善工人的工作环境。 一、物联网…

9.13号作业

1> 将之前定义的栈类和队列类都实现成模板类 栈的模块类 #include <iostream> using namespace std;template <typename T> class Stack { private:T data[40]{0};T top-1; public:Stack (){cout<<"这是构造函数"<<endl;}int stack_e…