当前位置: 首页 > news >正文

算法初识-时间复杂度空间复杂度

注:观看Adbul Bari算法视频

算法概念

 算法:先验分析,不依托于硬件,无语言限制,逻辑。
 程序:后验测试,依托硬件,语言限制,实现。

特点:

  • 输入-0或多个
  • 输出-至少一个
  • 确定性-人能理解
  • 有限性-有限集,时间集,必须有停止的时候
  • 有效性-没必要的语句不要写

准则:

  1. 时间:要高效-时间函数    f(n)=n  每行语句占一个单位时间
  2. 空间:占用内存                s(n)=n  每个参数占一个字
  3. 数据传输,宽带消耗(有必要传输很多数据吗,有优化空间吗)
  4. 设备消耗的功率
  5. CPU寄存器的消耗

频率计数法

1.一维数组之和
f(n) = 2n+3    s(n) = n+3     时间和空间复杂度都是O(n)

s=0                  ---1
for(i=0;i<n;i++){    --- 1,n+1,ns=s+A[i];         --- n
}
return s;            --- 1
s,i,n,A[i]           --- 1,1,1,n

2.二维数组之和
f(n) = 2n2+2n+1    s(n) = 3n2+3    时间和空间都是O(n2)

for(i=0;i<n;i++){               ---n+1for(j=0;j<n;j++){            ---nx(n+1)C[i,j] = A[i,j]+B[i,j];   ---nxn}
}
C,B,A,i,j,n                     ---nxn,nxn,nxn,1,1,1

3.二维矩阵之积
f(n) = 2n3+2n2+2n+1    s(n) = 3n2+4     时间复杂度O(n3),空间复杂度O(n2)

for(i=0;i<n;i++){for(j=0;j<n;j++){for(k=0;k<n;k++){C[i,j] = C[i,j] + A[i,k]*B[k,j];}}
}

4.总结规律:只关心循环里面的语句执行多少次,只关心最高次方!(因为是加法,并不会叠加次方,所以只关心循环里面就可以。换句话说只关心最高次方的那一条语句就可以)
请添加图片描述
请添加图片描述

时间函数的追踪分析法(举例)

for循环为例

例1:
请添加图片描述
例2:请添加图片描述
例3:
请添加图片描述
请添加图片描述
例4:请添加图片描述
例5:请添加图片描述
例6:请添加图片描述
总结:i自增或自减的情况都是O(n);i是乘法或者除法自增或自减的情况都是O(logn);其余情况用追踪分析法。

while循环为例

while循环一定要分析,规律性较小
请添加图片描述
请添加图片描述

渐进符号

定义

三种渐进符号随便用哪个都可以,但是在用O和omega时,尽量使用接近theta否则没有意义!
请添加图片描述

函数比较方法

1.可以直接带入数值,来直观的看出谁大谁小(用很大数值代入会更直观)
2.可以用log比较法
请添加图片描述
请添加图片描述
请添加图片描述

应用

请添加图片描述

函数的best/worst/avg情况

这种最好最坏情况无论使用哪种渐进符号都可以,函数的好坏情况不取决于渐进符号,渐进符号只是个表示方式而已。
一般平均情况接近于最坏情况。
请添加图片描述
二叉搜索树特点:左边的元素小于右边的元素。普通二叉树就是无序的。
其中关于w(n)=树高,minW(n) = logn,maxW(n)=n
请添加图片描述
任何形式的数据都可以通过寻找/合并形成二叉搜索树以此来看时间复杂度请添加图片描述

相关文章:

算法初识-时间复杂度空间复杂度

注&#xff1a;观看Adbul Bari算法视频 算法概念 算法&#xff1a;先验分析&#xff0c;不依托于硬件&#xff0c;无语言限制&#xff0c;逻辑。 程序&#xff1a;后验测试&#xff0c;依托硬件&#xff0c;语言限制&#xff0c;实现。 特点&#xff1a; 输入-0或多个输出-至…...

MySQL8.0.40编译安装(Mysql8.0.40 Compilation and Installation)

MySQL8.0.40编译安装 近期MySQL发布了8.0.40版本&#xff0c;与之前的版本相比&#xff0c;部分依赖包发生了变化&#xff0c;因此重新编译一版&#xff0c;也便于大家参考。 1. 下载源码 选择对应的版本、选择源码、操作系统 如果没有登录或者没有MySQL官网账号&#xff0…...

一个简单的跨平台Python GUI自动化 AutoPy

象一下&#xff0c;你坐在电脑前&#xff0c;手指轻轻一点&#xff0c;鼠标自己动了起来&#xff0c;键盘仿佛被无形的手操控&#xff0c;屏幕上的任务自动完成——这一切不需要你费力&#xff0c;只靠几行代码就能实现。这就是AutoPy的魅力&#xff0c;一个简单却强大的跨平台…...

C++中常见函数

目录 stringstream ss(line); 为什么使用 stringstream while(ss>>num){} arr.push_back(num); numeric_limits ::min() pair result throw invalid_argument(""); vector arr;和int arr[];有什么区别&#xff1f; 数据结构的本质 内存管理 功能与易用…...

C++: 类型转换

C: 类型转换 &#xff08;一&#xff09;C语言中的类型转换volatile关键字 修饰const变量 &#xff08;二&#xff09;C四种强制类型转换1. static_cast2. reinterpret_cast3. const_cast4. dynamic_cast总结 (三)RTTI &#xff08;一&#xff09;C语言中的类型转换 在C语言中…...

Linux驱动开发进阶(五)- 系统调用

文章目录 1、前言2、阻塞与非阻塞IO2.1、阻塞方式2.2、非阻塞方式2.3、小结 3、异步IO3.1、poll3.2、select3.3、epoll3.4、poll和epoll示例比较3.5、异步通知 4、unlocked_ioctl5、sysfs_notify 1、前言 学习参考书籍以及本文涉及的示例程序&#xff1a;李山文的《Linux驱动开…...

深度解析:文件或目录损坏且无法读取的应对之道

引言 在数字化办公与数据存储日益普及的今天&#xff0c;我们时常会遭遇各种数据问题&#xff0c;其中“文件或目录损坏且无法读取”这一状况尤为令人头疼。无论是个人用户存储在电脑硬盘、移动硬盘、U盘等设备中的重要文档、照片、视频&#xff0c;还是企业服务器上的关键业务…...

农业股龙头公司有哪些?

农业股票的龙头公司通常是指在农业领域具有较高市场份额、较强品牌影响力和较好财务表现的企业。以下是一些国内外知名的农业龙头公司&#xff1a; 国内农业龙头公司 中国中化 - 作为国内最大的化肥生产企业之一&#xff0c;主要从事化肥、种子、农药等产品的生产和销售。丰乐…...

【正点原子】如何设置 ATK-DLMP135 开发板 eth0 的开机默认 IP 地址

开机就想让 eth0 乖乖用静态 IP&#xff1f;别再被 DHCP 抢走地址了&#xff01; 三步教你彻底掌控 ATK-DLMP135 的网络启动配置&#xff0c;简单粗暴&#xff0c;实测有效&#xff01; 正点原子STM32MP135开发板Linux核心板嵌入式ARM双千兆以太网CAN 1. 删除 dhcpcd 自动获取…...

pyenv-virtualenv(python 版本管理工具)

推荐参考&#xff08;本人实测有用&#xff09; 参考文章pyenv 和 pyenv-virtualenv 的安装、配置和使用&#xff08;仅供参考&#xff09; 参考文章 pyenvpyenv-virtualenv&#xff08;仅供参考&#xff09; pyenv (windows)安装 手动安装 git clone https://github.com/pye…...

Solr admin 更新文档

<add><doc><field name"id">1904451090351546368</field><field name"companyName" update"set">测试科技有限公司</field></doc> </add>...

华为交换机上配置流量策略根据IP限速

一、配置ACL匹配目标IP 目的&#xff1a;通过ACL识别需要限速的IP地址或网段。 # 进入系统视图 system-view # 创建基本ACL&#xff08;例如ACL 3000&#xff09; acl 3000 rule 5 permit ip source 192.168.1.10 0 # 匹配单个IP&#xff08;源地址&#xff09; # 或匹配…...

3D数据共享标准——GLB文件格式揭秘

GLB 文件格式&#xff1a;跨平台 3D 数据共享的标准 简介 在这个数据爆炸的时代&#xff0c;3D 数据因其直观、逼真的特点而得到广泛应用。然而&#xff0c;不同 3D 软件和平台之间的兼容性一直是一个难题。 为了解决这一问题&#xff0c;GLB 文件格式应运而生。作为一种标准…...

Java 大视界 -- 基于 Java 的大数据隐私保护在金融客户信息管理中的实践与挑战(178)

&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎来到 青云交的博客&#xff01;能与诸位在此相逢&#xff0c;我倍感荣幸。在这飞速更迭的时代&#xff0c;我们都渴望一方心灵净土&#xff0c;而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识&#xff0c;也…...

基于springboot体育俱乐部预约管理系统(源码+lw+部署文档+讲解),源码可白嫖!

摘要 随着我国经济的高速发展与人们生活水平的日益提高&#xff0c;人们对生活质量的追求也多种多样。尤其在人们生活节奏不断加快的当下&#xff0c;人们更趋向于足不出户解决生活上的问题&#xff0c;线上管理系统展现了其蓬勃生命力和广阔的前景。与此同时&#xff0c;在科…...

【HTML-CSS】

一、概念 1、HTML 2、CSS 二、入门 HTML 教程 | 菜鸟教程 1、构架 注&#xff1a; 1、标签不区分大小写 2、属性可以使用单引号&#xff0c;也可以使用双引号 3、语法结构不严谨&#xff0c;但建议好好写 2、常见标签和样式 &#xff08;1&#xff09;标题 <span>没…...

UI自动化基础(1)

1、pip install selenium4.3.0&#xff0c;最好指定版本安装&#xff0c;因为不同的版本可能会有一些兼容 性的问题。 2、pip uninstall urllib3 &#xff0c;pip install urllib31.26.15 【执行版本安装】&#xff0c;goole是114.版本 3、装好浏览器&#xff0c;正确安装。最好…...

看雪 get_pwn3(2016 CCTF 中的 pwn3)

get_pwn3(2016 CCTF 中的 pwn3) 格式化字符串漏洞 get_pwn3(2016 CCTF 中的 pwn3) (1) motalymotaly-VMware-Virtual-Platform:~/桌面$ file pwn3 pwn3: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, …...

JAVA类和对象

实验目的&#xff1a; 1.掌握 Java 语言中类的定义、对象的创建、对象引用方法。 2.初步了解面向对象设计方法。 第一题&#xff1a; 设计一个自动铅笔类 AutoPencil&#xff0c;有 1 个属性 boolean penPoint&#xff08;笔尖是否伸出&#xff09;&#xff0c;有 4 个函数&a…...

c#程序结构

C# 程序结构 一个 C# 程序主要包括以下部分&#xff1a; 命名空间声明&#xff08;Namespace declaration&#xff09;一个 classClass 方法Class 属性一个 Main 方法语句&#xff08;Statements&#xff09;& 表达式&#xff08;Expressions&#xff09;注释 C# 文件的…...

988主材订购单

每一个大项&#xff0c;都可以添加多行小项&#xff0c; 小项里的品牌&#xff0c;型号规格&#xff0c;单位都是下来框&#xff0c;数据是后台传过来的。是一个多维数组。 <view style"width: 150rpx;color:#000;position:relative">备注&#xff1a;</vie…...

elementui table禁用全选,一次限制勾选一项。

1、设置属性&#xff1a;selection-change“handleSelectionChange” <el-table:data"taskList"ref"tableDataRefs"selection-change"handleSelectionChange":header-cell-class-name"hideAllCheckbox">function handleSelecti…...

Invalid Executable The executable contains bitcode

xcode 升级到16之后项目运行调试都没有问题&#xff0c;但是最后在上传到appstore的时候出现问题了 比如这种类似的错误&#xff0c;网上查了一下解决方法 解决方案&#xff1a; 执行一下指令删除该framework的bitcode xcrun bitcode_strip ${framework_path} -r -o ${framewo…...

【天梯赛】L2_005 集合相似度(C++)

L2-005 集合相似度 - 团体程序设计天梯赛-练习集 代码实现&#xff08;C&#xff09; #include <iostream> #include <vector> #include <unordered_set> #include <iomanip>// 计算两个集合的相似度 double cal(const std::unordered_set<int>…...

Java【多线程】(7)常见的锁策略

目录 1.前言 2.正文 2.1悲观锁和乐观锁 2.2重量级锁和轻量级锁 2.3挂起等待锁和自旋锁 2.4互斥锁与读写锁 2.5可重入锁与不可重入锁 2.6公平锁与不公平锁 2.7synchronized优化 2.7.1锁升级 2.7.2锁消除 2.7.3锁粗化 3.小结 1.前言 哈喽大家好&#xff0c;今天来给…...

Android Compose 中获取和使用 Context 的完整指南

在 Android Jetpack Compose 中&#xff0c;虽然大多数 UI 组件不再需要直接使用 Context&#xff0c;但有时你仍然需要访问它来执行一些 Android 平台特定的操作。以下是几种在 Compose 中获取和使用 Context 的方法&#xff1a; 1. 使用 LocalContext 这是 Compose 中最常用…...

车载通信基础 --- 解密公开密钥基础设施(PKI)

我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&#xff1a; 周末洗了一个澡&#xff0c;换了一身衣服&#xff0c;出了门却不知道去哪儿&#xff0c;不知道去找谁&am…...

深度强化学习基础 1:以狗狗学习握手为例

强化学习共同框架 在这个狗狗学习握手的场景中&#xff0c;强化学习的各个要素可以这样理解: 状态s(state): 狗狗所处的环境状况&#xff0c;比如主人伸出手掌的姿势、狗狗自身的姿势、周围的环境等。状态s描述了狗狗在特定时刻所感知到的环境信息。 动作a(action): 狗狗可以…...

【Kafka基础】topics命令行操作大全:高级命令解析(2)

1 强制删除主题 /export/home/kafka_zk/kafka_2.13-2.7.1/bin/kafka-topics.sh --delete \--zookeeper 192.168.10.33:2181 \--topic mytopic \--if-exists 参数说明&#xff1a; --zookeeper&#xff1a;直接连接Zookeeper删除&#xff08;旧版本方式&#xff09;--if-exists&…...

【redis】简介及在springboot中的使用

redis简介 基本概念 Redis&#xff0c;英文全称是Remote Dictionary Server&#xff08;远程字典服务&#xff09;&#xff0c;是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库&#xff0c;并提供多种语言的API。 与MySQL数据库不…...

Windwos的DNS解析命令nslookup

nslookup 解析dns的命令 有两种使用方式&#xff0c;交互式&命令行方式。 交互式 C:\Users\Administrator>nslookup 默认服务器: UnKnown Address: fe80::52f7:edff:fe28:35de> www.baidu.com 服务器: UnKnown Address: fe80::52f7:edff:fe28:35de非权威应答:…...

Vue.js 实现下载模板和导入模板、数据比对功能核心实现。

在前端开发中&#xff0c;数据比对是一个常见需求&#xff0c;尤其在资产管理等场景中。本文将基于 Vue.js 和 Element UI&#xff0c;通过一个简化的代码示例&#xff0c;展示如何实现“新建比对”和“开始比对”功能的核心部分。 一、功能简介 我们将聚焦两个核心功能&…...

通过世界排名第一的免费开源ERP,构建富有弹性的智能供应链

概述 现行供应链模式的结构性弱点凸显了对整个行业进行重塑的必要性。正确策略和支持可以帮助您重塑供应链&#xff0c;降低成本&#xff0c;实现业务转型。开源智造&#xff08;OSCG&#xff09;所推出的Odoo免费开源ERP解决方案&#xff0c;将供应链转化为具有快速响应能力的…...

自动驾驶数据闭环中的MLOps实践:Kubernetes、Kubeflow与PyTorch的协同应用

目录 1. 引言 2. 系统架构与技术栈 2.1 Kubernetes&#xff1a;弹性可伸缩的计算资源池 2.2 Kubeflow&#xff1a;端到端的MLOps工作流 2.3 PyTorch分布式训练&#xff1a;高效的模型训练引擎 3. 增强型数据处理技术 3.1 联邦学习聚合 3.2 在线学习更新 3.3 角落案例挖…...

如何在Linux中更改主机名?修改主机最新方法

hostname是一个Linux操作系统的常用功能&#xff0c;允许识别服务器&#xff0c; 这可用于容易地确定两个服务器之间的差异。 除了服务器的个人识别&#xff0c;主机名与大多数网络进程一起使用&#xff0c;其他应用程序也可能依赖于此&#xff0c;本期将指导大家如何在Linux中…...

分盘,内网

分盘 查看创建分区 # 查看磁盘信息&#xff08;确认目标磁盘&#xff0c;如/dev/sda&#xff09; lsblkfdisk -l# 启动fdisk工具&#xff08;需root权限&#xff09; sudo fdisk /dev/sda# 步骤1&#xff1a;删除旧分区表&#xff08;谨慎操作&#xff01;&#xff09; Comma…...

SQL122 删除索引

alter table examination_info drop index uniq_idx_exam_id; alter table examination_info drop index full_idx_tag; 描述 请删除examination_info表上的唯一索引uniq_idx_exam_id和全文索引full_idx_tag。 后台会通过 SHOW INDEX FROM examination_info 来对比输出结果。…...

【SQL】子查询详解(附例题)

子查询 子查询的表示形式为&#xff1a;(SELECT 语句)&#xff0c;它是IN、EXISTS等运算符的运算数&#xff0c;它也出现于FROM子句和VALUES子句。包含子查询的查询叫做嵌套查询。嵌套查询分为相关嵌套查询和不想关嵌套查询 WHERE子句中的子查询 比较运算符 子查询的结果是…...

AI和传统命理的结合

deepseek的火热 也带来了AI命理学的爆火 1. 精准解析&#xff1a;AI加持&#xff0c;数据驱动 通过先进的人工智能算法&#xff0c;我们对海量的传统命理知识进行了深度学习和整合。无论是八字排盘、紫微斗数&#xff0c;还是风水布局、生肖运势&#xff0c;AI都能根据您的个…...

Java设计模式之抽象工厂模式:从入门到架构级实践

设计模式是构建高质量软件的基石&#xff0c;而抽象工厂模式作为创建型模式的代表&#xff0c;不仅解决了对象创建的问题&#xff0c;更在架构设计中扮演着关键角色。本文将从基础到高阶、从单机到分布式&#xff0c;全面剖析抽象工厂模式的应用场景与实战技巧。 一、从问题出发…...

摄像头模块对焦方式的类型

摄像头模块的对焦方式直接影响成像清晰度和使用场景适应性&#xff0c;不同技术各有其优缺点。以下是常见对焦方式及其原理、特点和应用场景的详细说明&#xff1a; ‌1. 固定对焦&#xff08;Fixed Focus&#xff09;‌ ‌原理‌&#xff1a;镜头固定在特定距离&#xff08;…...

九屏图分析法以手机为例

九屏图的两种视角​​ ​​时间九屏图​​&#xff1a;关注系统的​​时间演化​​&#xff08;过去、现在、未来&#xff09;&#xff0c;强调技术或产品的生命周期。​​空间九屏图​​&#xff1a;关注系统的​​层次结构​​&#xff08;子系统、本系统、超系统&#xff0…...

【模板】前缀和

链接&#xff1a;【模板】前缀和 题目描述 给定一个长度为n的数组a1,a2,....ana_1, a_2,....a_na1​,a2​,....an​. 接下来有q次查询, 每次查询有两个参数l, r. 对于每个询问, 请输出alal1....ara_la_{l1}....a_ral​al1​....ar​ 输入描述: 第一行包含两个整数n和q. 第…...

微信小程序多线程的使用

微信小程序的多线程主要通过 Worker 实现&#xff0c;用于处理复杂计算任务以避免阻塞主线程。以下是完整的使用指南和最佳实践&#xff1a; 一、Worker 核心机制 运行环境隔离 主线程与 Worker 线程内存不共享通信通过 postMessage 完成&#xff08;数据拷贝而非共享&#xff…...

FPGA设计职位介绍|如何成为一名合格的数字前端设计工程师?

近年来FPGA行业持续升温&#xff0c;随着国产替代浪潮的加快推进&#xff0c;国家对可重构计算、边缘计算、自主可控等领域的扶持力度不断加大&#xff0c;FPGA作为灵活性高、可编程性强的重要芯片种类&#xff0c;在人工智能、通信、工业控制等应用中广受青睐。FPGA人才长期紧…...

Shell 基础

刷题&#xff1a; 思维导图&#xff1a; #include <stdio.h> // 手动定义32位有符号整数的范围 #define INT_MAX 2147483647 #define INT_MIN (-2147483647 - 1) int reverse(int x) { int rev 0; // 初始化反转后的数字为0 while (x ! 0) { // 当x不为0时&#xff…...

软件信息安全性测试如何进行?有哪些注意事项?

随着信息技术的高速发展&#xff0c;软件已经成为我们生活和工作中不可或缺的一部分。然而&#xff0c;随着软件产品的广泛普及&#xff0c;软件信息安全性问题也日益凸显&#xff0c;因此软件信息安全性测试必不可少。那么软件信息安全性测试应如何进行呢?在进行过程中又有哪…...

ragflow开启https访问:浏览器将自签证书添加到受信任的根证书颁发机构 ,当证书过期,还需要添加吗?

核心机制解析 信任链原理: 当您将自签名证书添加到"受信任的根证书颁发机构"后,系统会永久信任该证书的颁发者身份但证书本身的有效期和密钥匹配仍需验证证书更新的两种情况: 相同密钥续期:如果新证书使用相同的密钥对,浏览器通常会保持信任重新生成密钥:如果执…...

ragflow开启https访问:自签证书到期了,如何自动生成新证书

自动生成和更新自签名证书的方案 对于使用公网IP和自签名证书的RagFlow服务,要实现证书的自动生成和更新,可以采用以下方案: 方案一:使用脚本自动更新(推荐) 1. 创建自动更新脚本 在服务器上创建 ./docker/nginx/auto_renew_cert.sh 文件: #!/bin/bash# 证书路径 C…...

LLM面试题八

推荐算法工程师面试题 二分类的分类损失函数&#xff1f; 二分类的分类损失函数一般采用交叉熵(Cross Entropy)损失函数&#xff0c;即CE损失函数。二分类问题的CE损失函数可以写成&#xff1a;其中&#xff0c;y是真实标签&#xff0c;p是预测标签&#xff0c;取值为0或1。 …...