算法复杂度之大O复杂度表示法及空间复杂度

目录

简介

时间复杂度

大O复杂度表示法

空间复杂度


前言-与正文无关

        生活远不止眼前的苦劳与奔波,它还充满了无数值得我们去体验和珍惜的美好事物。在这个快节奏的世界中,我们往往容易陷入工作的漩涡,忘记了停下脚步,感受周围的世界。让我们一起提醒自己,要适时放慢脚步,欣赏生活中的每一道风景,享受与家人朋友的温馨时光,发现那些平凡日子里隐藏的幸福时刻。因为,这些点点滴滴汇聚起来的,才是构成我们丰富多彩生活的本质。希望每个人都能在繁忙的生活中找到自己的快乐之源,不仅仅为了生存而工作,更为了更好的生活而生活。

        送你张美图!希望你开心!

简介

数据结构和算法本质上是""。所以代码的执行效率是非常重要的度量,我们采用时间复杂度和空间复杂度来计算

时间复杂度

O复杂度表示法

大O符号(Big O notation)是一种数学符号,用于描述算法的时间复杂度,即算法执行所需时间与输入数据大小之间的关系。O 代表了“Order of”(阶),它后面跟着的是一个函数,这个函数表示了算法复杂度随输入大小增加的增长率。

我们经常可以在各种数据结构看到,O(n)、O(logn)之类的数据,但往往却不知道其意,下面我给介绍一下吧。

  • O(1) - 常数时间复杂度: 无论数据量如何,算法所需时间都是固定的。例如,访问数组中的元素长度,长度length早就被存起来了随时可以取长度是多少。

  • O(n) - 线性时间复杂度: 算法执行时间与输入数据的大小成正比。例如,遍历数组或链表。

如下面代码,每行代码执行时间为t,当你入参为n时,for循环就是t*n,T(n):代表代码执行时间。总时间就是T(n)=3t+2tn。当n无限大时,低阶、常量、系数都可以忽略,当然你可以看到决定你代码核心时间因素不是t,因为t是固定的,那么你忽略下3t 和 t和2,也就是n ,即上例中的时间复杂度为O(n),也就是代码执行时间随着数据规模的增加而增长

int sum(int n){
    int s=0; //t
    int i=1; //t
    for(;i<=n;i++){ //t*n
        s=s+i; //t*n
    }
    return s; //t
}
  • O(log n) - 对数时间复杂度: 随着输入数据的增加,所需时间的增长速度会逐渐减慢。二分查找就是一个典型的 O(log n) 算法。(相对于O(n),如果你的算法是这个,那么就代表他很完美)

下述是个二分查找法,可以看到通过算法将数据查询复杂度减半

public class BinarySearch {

    public static int binarySearch(int[] array, int value) {
        int low = 0;
        int high = array.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // 防止溢出的写法
            int midVal = array[mid];

            if (midVal < value) {
                low = mid + 1;
            } else if (midVal > value) {
                high = mid - 1;
            } else {
                return mid; // 找到元素,返回其索引
            }
        }
        return -1; // 元素未找到
    }

    public static void main(String[] args) {
        int[] arr = {-22, -15, 1, 7, 20, 35, 55}; // 假定数组已排序
        int searchValue = 20;
        int resultIndex = binarySearch(arr, searchValue);

        if (resultIndex >= 0) {
            System.out.println("在索引处找到的元素: " + resultIndex);
        } else {
            System.out.println("在数组中找不到元素.");
        }
    }
}
  • O(n log n) - 线性对数时间复杂度: 这通常出现在执行了 O(log n) 复杂度的操作 n 次,如快速排序和归并排序。

  • O(n^2) - 平方时间复杂度: 时间复杂度与输入数据的平方成正比。例如,两层嵌套循环。n^2就是n的2次方,下面其他例子看到^,也可以这么理解!

int sum(int n){
    int s=0;
    int i=1;
    int j=1;
    for(;i<=n;i++){// n
        j=1;
    for(;j<=m;j++){ //n*m
        s=s+i+j; //n*m
        }
    }
    return s;
}
  • O(2^n) - 指数时间复杂度: 算法的运行时间随输入大小呈指数增长。很多递归算法(如计算斐波那契数列的简单实现)具有这样的时间复杂度。

  • O(n!) - 阶乘时间复杂度: 算法的运行时间与输入数据的阶乘成正比,这通常出现在解决排列问题时

空间复杂度

空间复杂度全称是渐进空间复杂度,表示算法的存储空间与数据规模之间的增长关系,这个解释起来就比如我们的内存可能就1G要运行上亿数据,如果一次运行太多有内存溢出风险。
比如将一个数组拷贝到另一个数组中,就是相当于空间扩大了一倍:T(n)=O(2n),T(n)是代码执行时间 ,忽略系数,即为O(n),这是一个非常常见的空间复杂度,比如跳跃表、 hashmap 的扩容
此外还有 :O(1) ,比如原地排序、 O(n ) 此种占用空间过大
由于现在硬件相对比较便宜,所以在开发中常常会利用空间来换时间,比如缓存技术 。典型的数据结构中空间换时间是:跳跃表 。
在实际开发中我们也更关注代码的时间复杂度,而用于执行效率的提升,空间因为现在空间都很不值钱了所以不必担心了解即可!

------------------------------------------与正文内容无关------------------------------------
 如果觉的文章写对各位读者老爷们有帮助的话,麻烦点赞加关注呗!作者在这拜谢了!

混口饭吃了!如果你需要Java 、Python毕设、商务合作、技术交流、就业指导、技术支持度过试用期。请在关注私信我,本人看到一定马上回复!

这是我全部文章所在目录,看看是否有你需要的,如果遇到觉得不对地方请留言,看到后我会查阅进行改正。

A乐神-CSDN博客

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

EasyX图形库学习(一、窗口创建函数initgraph、背景颜色设置setbkcolor、图形绘制函数)

目录 一、easyX图形库基本介绍 1、easyX的原理 2、easyX的安装 3、easyX的颜色&#xff08;RGB颜色模型&#xff09; 颜色模型相关函数: 4、easyX的坐标 二、相关函数介绍: 绘图设备相关函数&#xff1a; 图形颜色及样式设置相关函数: 图形绘制相关函数: 文字输出相关…

【Springcloud篇】学习笔记十一(十八章):Seata解决分布式事务问题

第十八章_Seata解决分布式事务问题 1.Seata简介 1.1分布式事务问题由来 分布式前 单机单库没这个问题从1:1 -> 1:N -> N:N 单体应用被拆分成微服务应用&#xff0c;原来的三个模块被拆分成三个独立的应用,分别使用三个独立的数据源&#xff0c;业务操作需要调用三个…

ref和reactive, toRefs的使用

看尤雨溪说&#xff1a;为什么Vue3 中应该使用 Ref 而不是 Reactive&#xff1f; toRefs import { ref, toRefs } from vue;// 定义一个响应式对象 const state ref({count: 0,name: Vue });// 使用toRefs转换为响应式引用对象 const reactiveState toRefs(state);// 现在你…

BUG:docker启动之后直接退出问题

示例如下&#xff1a; 问题排查&#xff1a; 启动命令 sudo docker run --privilegedtrue --runtimenvidia --shm-size80g -v /mmm_data_center:/mmm_data_center -v /imagecenter_new/:/imagecenter_new -v /data1:/data1 -v /mnt/offline_data/:/mnt/offline_data/ --neth…

python 基础知识点(蓝桥杯python科目个人复习计划32)

今日复习内容&#xff1a;基础算法中的位运算 1.简介 位运算就是对二进制进行操作的运算方式&#xff0c;分为与运算&#xff0c;或运算&#xff0c;异或运算&#xff0c;取反&#xff0c;左移和右移。 &#xff08;1&#xff09;与运算 xyx&y000010100111 (2)或运算 …

UE5动画源码剖析

重点剖析的类&#xff1a; UAnimationInstanceFAnimInstanceProxy 参考&#xff1a;https://zhuanlan.zhihu.com/p/405437842 参考&#xff1a;https://blog.csdn.net/qq_23030843/article/details/109103433 参考&#xff1a;https://ikrima.dev/ue4guide/gameplay-programm…

vue实现带缩略图的轮播图(vue-awesome-swiper)

demo 请复制打开 https://download.lllomh.com/cliect/#/product/E125504451206525 如点击链接跳转失败请复制网址到浏览器打开 1.引入swiper和vue-awesome-swiper插件 npm install swiper4 --save npm install vue-awesome-swiper3 --save2.在main.js中引入&#xff1a; …

vue插槽

1.插槽使用 正常渲染子组件时&#xff0c;如果子组件的起始标签和闭合标签内有内容&#xff0c;内容是无法被渲染出来的&#xff0c;如下图&#xff1a; // Son.vue <template><div>子组件</div> </template>// Parent.vue<Son>123123123</S…

vue3 之 项目创建

1.使用create-vue创建项目 前提环境条件 已安装 16.0 或更高版本的 Node.js 创建一个Vue应用 npm init vuelatest 这一指令将会安装并执行 create-vue 2.熟悉项目目录和关键文件

【数据结构与算法】(5)基础数据结构之队列 链表实现、环形数组实现详细代码示例讲解

目录 2.4 队列1) 概述2) 链表实现3) 环形数组实现 2.4 队列 1) 概述 计算机科学中&#xff0c;queue 是以顺序的方式维护的一组数据集合&#xff0c;在一端添加数据&#xff0c;从另一端移除数据。习惯来说&#xff0c;添加的一端称为尾&#xff0c;移除的一端称为头&#xf…

STM32学习笔记(五) —— 按键翻转LED

前面我们分析过GPIO的各个寄存器&#xff0c;探讨了如何使用GPIO点亮LED&#xff0c;这里再验证一下GPIO的输入功能 1.硬件连接 我们在开发板上将按键连接到了PA0引脚&#xff0c;按键外接了上拉电阻&#xff0c;默认状态下PA0引脚处于高电平&#xff0c;当按键按下&#xff0…

七月论文审稿GPT第2.5版:微调GPT3.5 turbo 16K和llama2 13B以扩大对GPT4的优势

前言 我司自去年7月份成立大模型项目团队以来&#xff0c;至今已有5个项目组&#xff0c;其中 第一个项目组的AIGC模特生成系统已经上线在七月官网第二项目组的论文审稿GPT则将在今年3 4月份对外上线发布第三项目组的RAG知识库问答第1版则在春节之前已就绪至于第四、第五项目…

【stm32】hal库学习笔记-ADC模数转换(超详细!)

【stm32】hal库学习笔记-ADC模数转换&#xff08;超详细&#xff01;&#xff09; 本篇章介绍了ADC实现电压检测的三种方式 ADC原理及选型 ADC将连续的模拟电压信号转换为二进制的数字信号 选型参数 速度&#xff08;采样频率&#xff09; 功耗 精度 转换原理 ADC hal库驱…

一、Redis之NoSQL

1.1 什么是NoSQL NoSQL&#xff08;Not Only SQL&#xff09;即不仅仅是SQL&#xff0c;泛指非关系型的数据库&#xff0c;它可以作为关系型数据库的良好补充。随着互联网web2.0网站的兴起&#xff0c;非关系型的数据库现在成了一个极其热门的新领域&#xff0c;非关系数据库产…

[Linux 进程控制(二)] 写时拷贝 - 进程终止

文章目录 1、写时拷贝2、进程终止2.1 进程退出场景2.1.1 退出码2.1.2 错误码错误码 vs 退出码2.1.3 代码异常终止引入 2.2 进程常见退出方法2.2.1 exit函数2.2.2 _exit函数 本片我们主要来讲进程控制&#xff0c;讲之前我们先把写时拷贝理清&#xff0c;然后再开始讲进程控制。…

图论练习2

内容&#xff1a;路径计数DP&#xff0c;差分约束 最短路计数 题目大意 给一个个点条边的无向无权图&#xff0c;问从出发到其他每个点的最短路有多少条有自环和重边&#xff0c;对答案 解题思路 设边权为1&#xff0c;跑最短路 表示的路径数自环和重边不影…

基于OpenCV灰度图像转GCode的双向扫描实现

基于OpenCV灰度图像转GCode的双向扫描实现 引言激光雕刻简介OpenCV简介实现步骤 1.导入必要的库2. 读取灰度图像3. 图像预处理4. 生成GCode 1. 简化版的双向扫描2. 优化版的双向扫描 5. 保存生成的GCode6. 灰度图像双向扫描代码示例 总结 系列文章 ⭐深入理解G0和G1指令&…

【深入浅出Java性能调优】「底层技术原理体系」详细分析探索Java服务器性能监控Metrics框架的实现原理分析(Dropwizard度量基础案例指南)

深入探索Java服务器性能监控Metrics框架的实现原理分析 前提介绍Dropwizard MetricsDropwizard的特点Dropwizard的开发案例需要引入Maven依赖常用度量类型Meter(每秒请求数为单位测量请求率)定义度量核心MetricRegistry构建对应的Meter指标对象请求标记采样业务方法控制报告器…

利用Excel爬取网页数据

想要获取网页上的表格数据&#xff0c;可以通过Excel自带的功能&#xff0c;从网站导入数据&#xff0c;并且可以实时刷新最新数据。具体步骤如下&#xff1a; 1、新建Excel&#xff0c;打开&#xff0c;选择【数据】-【自网站】 2、在弹出的对话框中输入目标网址&#xff0c;…

Java常用

文章目录 基础基础数据类型内部类Java IOIO多路复用重要概念 Channel **通道**重要概念 Buffer **数据缓存区**重要概念 Selector **选择器** 关键字final 元注解常用接口异常处理ErrorException JVM与虚拟机JVM内存模型本地方法栈虚拟机栈 Stack堆 Heap方法区 Method Area (JD…