怎样计算一个算法的复杂度?

分析一个算法主要看这个算法的执行需要多少机器资源。在各种机器资源中,时间和空间是两个最主要的方面。因此,在进行算法分析时,人们最关心的就是运行算法所要花费的时间和算法中使用的各种数据所占用的空间资源。算法所花费的时间通常称为时间复杂度,使用的空间资源称为空间复杂度。接下来学习如何计算一个算法的时间复杂度和空间复杂度。

1.时间复杂度

在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,然后分析T(n)随n的变化。

1653989744854_41.png

这样用大写的O来标记算法的时间复杂度,称之为大O(Order的简写)标记法。一般随着n的增长,T(n)也会随之增长,其中T(n
)增长最慢者就是时间性能最优的算法。

在计算时间复杂度的时候,根据T(n)与n的最高阶数关系,我们给这些算法的复杂度进行了归类,如表1所示。
1653991095252_42.png

当然还会有一些其他阶数关系,这里只是列出了几种较常见的关系。算法的执行次数可能会与规模n呈现出这些关系,那么这些关系又是如何推导出来的呢?下面给出大O阶的推导方法:

(1)用常数1取代运行中的所有加法常数。

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

(3)如果最高阶项存在,且不是1,则除去其常系数,得到的结果就是大O阶。

接下来通过分析几段程序的执行过程来推导出其时间复杂度,程序段1代码如下所示:

int a=100;              //执行一次

int b=200;              //执行一次

int sum=a+b;            //执行一次

printf("&d\n",sum);      //执行一次

上述程序段有4行代码,每一行执行1次,加起来一共执行了4次,f(n)=4,即T(n)=O(4)。根据推导方法中的第一条,将常数项以1代替。在保留其最高阶项时,发现其没有最高阶项,因此该算法的时间复杂度为O(1),为常数阶。程序段2代码如下所示:

void func()
{
    int i,sum=0;                         //执行一次
    for (i=0;i<=100;i++)
    {
    sum +=i;                              //执行n次
    }

    printf("sd\n",sum);               //执行一次
}

该程序段的执行次数为1+n+1,则f(n)=n+2,即T(n)=O(n+2)。然后将常数项以1替换,且只保留最高阶项,则得出T(n)=O(n),因此该算法的时间复杂度为O(n),为线性阶。

程序段3代码如下所示:

void func()
{
    int i=l;
    do
    {
    i*=2}
    while (i<n);
}

在这个程序段中,当i<n时,循环结束。如果循环了f(n)次,则2(fn)=n,即f(n)=log2n,T(n)=O(log2n)。然后消除常系数,保留最高阶项,最后得出T(n)=O(logn),为对数阶。

用大O阶来推导算法的复杂度并不难,读者在以后的学习中设计算法,就可以用此法来估测算法的优劣。

2.空间复杂度

空间复杂度是对一个算法在运行过程中所占存储空间大小的度量,一般也作为问题规模n的函数,以数量级形式给出,格式如下所示:

1653992397625_43.png

一个算法的存储量包括输入数据所占空间、程序本身所占空间和辅助变量所占空间。在对算法进行分析时,只考虑辅助变量所占空间。若所需辅助空间相对于输入数据量来说是常数,则称此算法为原地工作。若所用空间量依赖于特定的输入,则除了有特殊说明外,均按最坏情况考虑。

有时候,在写代码时可以用空间来换取时间,例如,写一个算法来判断某年是否是闰年,这样每输入一个年份都要调用算法去判断一下,在时间上就有点复杂。为了提高效率,可以用空间来换取时间,即建立一个大小合适的数据,编号从0到n,如果是闰年,则存入数据1,否则存入数据0。这样只要通过判断年份编号上存储的是0还是1就知道该年份是否是闰年了。

用空间换取时间可以将运算最小化,但这两种情况哪种更好,要结合具体情况而定。一般情况下,都是用时间复杂度来度量算法,当不加限定地使用“复杂度”这一术语时,都是指时间复杂度。

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

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

相关文章

DataWhale AI夏令营——机器学习

DataWhale AI夏令营——机器学习 学习记录一1. 异常值分析2. 单变量箱线图可视化3. 特征重要性分析 学习记录2 (2023.07.27更新)1. 数据层面2. 特征工程3. 数据划分方式4. 后处理 学习记录一 锂电池电池生产参数调控及生产温度预测挑战赛 已配置环境&#xff0c;跑通baseline…

SpringCloud nacos 集成 gateway ,实现动态路由

&#x1f388; 作者&#xff1a;Linux猿 &#x1f388; 简介&#xff1a;CSDN博客专家&#x1f3c6;&#xff0c;华为云享专家&#x1f3c6;&#xff0c;Linux、C/C、云计算、物联网、面试、刷题、算法尽管咨询我&#xff0c;关注我&#xff0c;有问题私聊&#xff01; &…

数据库架构设计

数据库架构设计 数据库架构分类 介绍 介绍常见的 四种 数据库架构设计模型&#xff1a; 单库架构、分组架构、分片架构和分组分片架构 &#xff0c;以及每种架构的 使用场景、存在的问题和对应的解决方案 。 一、数据模型 我们以 “ 用户中心 ” 数据库作为 数据模型 &…

python与深度学习(八):CNN和fashion_mnist二

目录 1. 说明2. fashion_mnist的CNN模型测试2.1 导入相关库2.2 加载数据和模型2.3 设置保存图片的路径2.4 加载图片2.5 图片预处理2.6 对图片进行预测2.7 显示图片 3. 完整代码和显示结果4. 多张图片进行测试的完整代码以及结果 1. 说明 本篇文章是对上篇文章训练的模型进行测…

Spring(二):更简单的存储与读取 Bean

通过上一章的Spring&#xff0c;我们基本实现了Spring 的读取与存储&#xff0c;但是在操作过程中&#xff0c;读取与存储并没有那么得“简单” 一套流程还是很复杂&#xff0c;所以&#xff0c;本章来介绍更加简单得读取与存储。 在 Spring 中想要更简单的存储和读取对象的核…

Rust vs Go:常用语法对比(八)

题目来自 Golang vs. Rust: Which Programming Language To Choose in 2023?[1] 141. Iterate in sequence over two lists Iterate in sequence over the elements of the list items1 then items2. For each iteration print the element. 依次迭代两个列表 依次迭代列表项1…

【数据结构】实验四:循环链表

实验四 循环链表 一、实验目的与要求 1&#xff09;熟悉循环链表的类型定义和基本操作&#xff1b; 2&#xff09;灵活应用循环链表解决具体应用问题。 二、实验内容 题目一&#xff1a;有n个小孩围成一圈&#xff0c;给他们从1开始依次编号&#xff0c;从编号为1的小孩开…

【项目开发】商城 - 三级分类 - 简单笔记

目录标题 后端业务类实体类 前端最终实现效果排序变化批量删除 后端 业务类 // 省略其他简单的CRUDOverridepublic List<CategoryEntity> listWithTree() {// 1、查出所有分类List<CategoryEntity> list baseMapper.selectList(null);// 2. 找出所有的一级分类Li…

数据库监控工具-PIGOSS BSM

PIGOSS BSM 运维监控系统的重要功能之一是数据库监控&#xff0c;它能够帮助数据库管理员(DBA)和系统管理员监控包含Oracle、SQL Server、MySQL、DB2、PostgreSql、MongoDB、达梦、南大通用、人大金仓、神州通用等多种类异构型的数据库环境。PIGOSS BSM通过执行数据库查询来采集…

【Spring Cloud Alibaba】限流--Sentinel

文章目录 概述一、Sentinel 是啥&#xff1f;二、Sentinel 的生态环境三、Sentinel 核心概念3.1、资源3.2、规则 四、Sentinel 限流4.1、单机限流4.1.1、引入依赖4.1.2、定义限流规则4.1.3、定义限流资源4.1.4、运行结果 4.2、控制台限流4.2.1、客户端接入控制台4.2.2、引入依赖…

基于深度学习的CCPD车牌检测系统(PyTorch+Pyside6+YOLOv5模型)

摘要&#xff1a;基于CCPD数据集的高精度车牌检测系统可用于日常生活中检测与定位车牌目标&#xff0c;利用深度学习算法可实现图片、视频、摄像头等方式的车牌目标检测识别&#xff0c;另外支持结果可视化与图片或视频检测结果的导出。本系统采用YOLOv5目标检测模型训练数据集…

【Spring篇】初识 Spring IoC 与 DI

目录 一. Spring 是什么 ? 二. 何为 IoC ? 三. 如何理解 Spring IoC ? 四. IoC 与 DI 五 . 总结 一. Spring 是什么 ? 我们通常所说的 Spring 指的是 Spring Framework&#xff08;Spring 框架&#xff09;&#xff0c;它是⼀个开源框架&#xff0c;有着活跃⽽ 庞⼤…

逻辑回归概述

逻辑回归介绍 1. 逻辑回归的应用场景 逻辑回归(Logistic Regression)是机器学习中的 一种分类模型 ,逻辑回归是一种分类算法,虽然名字中带有回归。由于算法的简单和高效,在实际中应用非常广泛 广告点击率是否为垃圾邮件是否患病信用卡账单是否会违约 逻辑回归就是解决二…

day14 | 100.二叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点个数

文章目录 一、二叉树的最大深度二、二叉树的最小深度三、完全二叉树的节点数 一、二叉树的最大深度 100.二叉树的最大深度 因为题给出的高度和深度是一样的&#xff0c;所以求得结果都能过。 class Solution { public:int getHeight(TreeNode *node){if (node nullptr)retu…

Pytest学习教程_基础知识(一)

前言 pytest是一个用于编写和执行Python单元测试的框架。它提供了丰富的功能和灵活性&#xff0c;使得编写和运行测试变得简单而高效。 pytest的一些主要特点和解释如下&#xff1a; 自动发现测试&#xff1a;pytest会自动查找以"test_"开头的文件、类和函数&#x…

腾讯 SpringBoot 高阶笔记,限时开源 48 小时,真香警告

众所周知&#xff0c;SpringBoot 最大的一个优势就是可以进行自动化配置&#xff0c;简化配置&#xff0c;不需要编写太多的 xml 配置文件&#xff1b;基于 Spring 构建&#xff0c;使开发者快速入门&#xff0c;门槛很低&#xff1b;SpringBoot 可以创建独立运行的应用而不需要…

【学习笔记】目标跟踪领域SOTA方法比较

目录 前言方法1 TraDeS:2 FairMOT:3 SMILEtrack:4 ByteTrack: 前言 常用于行人跟踪的多目标跟踪数据集包括&#xff1a;MOT 15/16/17/20、PersonPath22等… 为更好比较现有SOTA算法的检测性能&#xff0c;本博客将针对在各数据集上表现较优的算法模型进行介绍。&#xff08;表…

ip校园广播音柱特点

ip校园广播音柱特点IP校园广播音柱是一种基于IP网络技术的音频播放设备&#xff0c;广泛应用于校园、商业区、公共场所等地方。它可以通过网络将音频信号传输到不同的音柱设备&#xff0c;实现远程控制和集中管理。IP校园广播音柱具备以下特点和功能&#xff1a;1. 网络传输&am…

SSM框架 基础

1.数据库 2.工程 3.pom 4.web.xml 5.spring配置文件头部 6.实体类 7.StudentMapper接口 8. StudentMapper.xml 9.StudentService 10. StudentServiceImpl 11.StudentController 实战 查询所有 StudentMapper StudentService StudentServiceImpl StudentMapper.xml Stude…

效率与质量兼备的6个设计工具!

今天本文为大家推荐的这6个设计工具&#xff0c;将帮助设计师实现高效工作&#xff0c;同时也更好地展示自己的创作力&#xff0c;一起来看看吧&#xff01; 1、即时设计 即时设计是一款国内的设计工具&#xff0c;它为设计师提供了非常多实用的设计功能和精致的设计素材&…