了解时间复杂度和空间复杂度

在学习数据结构前,我们需要了解时间复杂度和空间复杂度的概念,这能够帮助我们了解数据结构。

算法效率分为时间效率和空间效率

时间复杂度

一个算法的复杂度与其执行的次数成正比。算法中执行基础操作的次数,为算法的时间复杂度。

我们采用大O的渐进表示法。

推导大O阶方法:
1用常数1取代运行时间中的所有加法常数
2在修改后的运行次数函数中,保留最高阶项。
3如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

有些算法的时间复杂度存在最好、平均和最坏情况:
最坏情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期望运行次数
最好情况:任意输入规模的最小运行次数(下界)

在实际中一般情况关注的是算法的最坏运行情况

举例:

冒泡排序的时间复杂度

 从这个例子我们知道了,不是一层循环时间复杂度就是N,两层就是N^2要看具体算法实现。

二分法时间复杂度分析:

 阶乘递归的时间复杂度

 空间复杂度

对临时储存空间占用大小的量度。计算的是变量的个数。

首先来看冒泡排序的时间复杂度

循环走了N次,重复利用的是一个空间。

斐波那契数列的空间复杂度:

 阶乘的时间复杂度:

算法题

消失的数字

面试题 17.04. 消失的数字 - 力扣(LeetCode)


 

思路1:

排序,如果后一个数字不等于前一个数字加1,那么前一个数字加1,就是要寻找的消失的数字。

这种方法的时间复杂度是N*lgN

思路2:

把0到N加起来,再减去各个数字,得到的数字就是消失的数字。这里的时间复杂度是O(N)。如果先累加,时间复杂度是0(N),依次遍历一遍为O(N)。

int missingNumber(int* nums, int numsSize){
    int N=numsSize;
    int ret=(0+N)*(N+1)/2;
    for(int i=0;i<numsSize;++i)
    {
        ret-=nums[i];
    }
    return ret;

}

思路3:

把数组中的所有数字跟0到N异或,剩下的数字就是消失的数字。(我们知道,x^x=0,0^x=x)



int missingNumber(int* nums, int numsSize){
    int N=numsSize;
    int x=0;
    for(int i=0;i<numsSize;i++)
    {
        x^=nums[i];//x将包含数组nums中所有元素的异或结果
    }
    for(int j=0;j<=N;j++)
    {
        x^=j;
    }
    return x;

}

189. 轮转数组 - 力扣(LeetCode)

思路1:旋转k次

void rotate(int* nums, int numsSize, int k) {
    //首先把最后一个数储存起来
    for(int i=0;i<k;i++)
    {
    int tmp=nums[numsSize-1];
    for(int i=numsSize-2;i>=0;i--)
    {
        nums[i+1]=nums[i];
    }
    nums[0]=tmp;
    }
}

思路2:三段逆置

前k个逆置

后k个逆置

再整体逆置

void Reverse(int*nums,int left,int right)
{
    while(left<right)
    {
        int tmp=nums[left];
        nums[left]=nums[right];
        nums[right]=tmp;
        left++;
        right--;
    }
}
void rotate(int* nums, int numsSize, int k) 
{
    if(k>=numsSize)
    {
        k%=numsSize;
    }
    Reverse(nums,numsSize-k,numsSize-1);
    Reverse(nums,0,numsSize-k-1);
    Reverse(nums,0,numsSize-1);
}

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

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

相关文章

Rust中的函数指针

什么是函数指针 通过函数指针允许我们使用函数作为另一个函数的参数。函数的类型是 fn &#xff08;使用小写的 ”f” &#xff09;以免与 Fn 闭包 trait 相混淆。fn 被称为 函数指针&#xff08;function pointer&#xff09;。指定参数为函数指针的语法类似于闭包。 函数指…

VIO外参标定方法总结

一、前言 VIO外参标定是指相机和IMU之间的转移矩阵的确定&#xff0c;包括33的旋转矩阵和3维平移向量。整体上分为离线标定和在线标定两类方法&#xff0c;这篇文章做一个总结&#xff0c;主要是经典的方法&#xff0c;记录其思想。 二、博文链接 1、离线标定方法 最基本的…

p0级故障-nptd和ntpdate用法

一、背景 绝对真实的大厂线上P0级故障经历分享。 某日凌晨3点&#xff0c;企业微信群变得热闹起来&#xff0c;想都不用想&#xff0c;作为互联网人&#xff0c;特别是运维相关的同学知道&#xff0c;肯定又是出故障了&#xff0c;并且这个故障还很大。 当前晚上我睡着了&#…

【Java EE】 文件IO的使用以及流操作

˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如…

【Qt】error LNK2001: 无法解析的外部符号 “__declspec(dllimport)

参考&#xff1a;Qt/VS LNK2019/LNK2001&#xff1a;无法解析的外部符号_qt lnk2001无法解析的外部符号-CSDN博客 微软官方报错文档-链接器工具错误 LNK2019 __declspec error LNK2001: 无法解析的外部符号 "__declspec(dllimport) 原因 以这种为前缀的基本上跟库相关…

Visual Studio安装MFC开发组件

MFC由于比较古老了&#xff0c;Visual Studio默认没有这个开发组件。最近由于一些原因&#xff0c;需要使用这个库&#xff0c;这就需要另外安装。 参考了网上的一些资料&#xff0c;根据实际使用&#xff0c;其实很多步骤不是必须的。 https://zhuanlan.zhihu.com/p/68117276…

HarmonyOS开发实战(黑马健康系列一:欢迎页)

系列文章目录 &#xff08;零&#xff09;鸿蒙HarmonyOS入门&#xff1a;如何配置环境&#xff0c;输出“Hello World“ &#xff08;一&#xff09;鸿蒙HarmonyOS开发基础 &#xff08;二&#xff09;鸿蒙HarmonyOS主力开发语言ArkTS-基本语法 &#xff08;三&#xff09;鸿蒙…

沐风老师3DMAX一键相框生成插件安装使用方法教程

3DMAX一键相框生成插件使用教程 3DMAX一键相框生成插件&#xff0c;用于根据导入的图像文件以正确的比例从选定的图像中快速创建相框。只需点击几下鼠标&#xff0c;它就可以同时创建多个相框&#xff0c;在尺寸、轮廓、颜色和玻璃方面有许多选项。 支持Corona、Vray和标准材质…

Java基础(运算符)

运算符 运算符和表达式 运算符&#xff1a;对字面量或者变量进行操作的符号 表达式&#xff1a;用运算符把字面量或者变量连接起来&#xff0c;符合java语法的式子就可以称为表达式&#xff1b;不同运算符连接的表达式体现的是不同类型的表达式。 算术运算符&#xff08;加…

Unity 按下Play键后,Scene View里面一切正常,但是Game View中什么都没有 -- Camera Clear Flags的设置

问题如下所示。 最先遇到这个问题是我想用Unity开发一个VR 360-degree Image Viewer。在Scene View中可以看到球体&#xff0c;但是Game View什么都看不到。最后找到的原因是&#xff0c;我使用的shader是Skybox/Panorama&#xff0c; 需要把Main Camera的Clear Flags设置成Do…

灌区信息化解决方案-大型灌区信息化改造

系统方案 灌区信息化解决方案主要对灌区的水情、渠道流量、土壤墒情、气象等信息进行监测&#xff0c;对重点区域进行视频监控&#xff0c;同时对泵站、闸门进行远程控制&#xff0c;实现信息的测量、统计、分析、控制、调度等功能。为灌区管理部门科学决策提供了依据&#xff…

多组学+机器学习+膀胱癌+分型+建模

这是一个基于多组学机器学习的分型建模文章&#xff0c;这里我们大概介绍一下&#xff0c;这篇文章做了啥 一、研究背景 1、尿路上皮癌是高度恶性的肿瘤&#xff0c;预后差&#xff0c;死亡率高 2、没有明显有效的治疗方法&#xff0c;多数患者在免疫治疗中无法受益&#xf…

Java混淆的重要性

在软件开发领域&#xff0c;安全性与代码保护一直是备受关注的问题。特别是在Java这样的跨平台语言中&#xff0c;保护源代码的机密性和完整性显得尤为重要。Java混淆作为一种代码保护技术&#xff0c;其在现代软件开发中的地位日益凸显。本文将详细探讨Java混淆的重要性&#…

【网络安全】网络安全协议和防火墙

目录 1、网络层的安全协议&#xff1a;IPsec 协议族 &#xff08;1&#xff09;IP 安全数据报格式 &#xff08;2&#xff09;互联网密钥交换 IKE (Internet Key Exchange) 协议 2、运输层的安全协议&#xff1a;TLS 协议 3、系统安全&#xff1a;防火墙与入侵检测 1、网络…

addr2line + objdump 定位crash问题

目录 背景 godbolt汇编工具 tombstone ARM平台汇编知识 寄存器介绍 常见汇编指令 函数入参及传递返回值过程 入参顺序 变参函数 虚函数表 典型问题分析过程 Crash BackTrace Addr2line objdump 拓展 为什么SetCameraId函数地址偏移是40(0x28) 参考 背景 最近在…

kerberos:介绍

文章目录 一、介绍二、kerberos框架1、名词解释2、框架 三、优缺点四、其他认证机制1、SSL2、OAuth3、LDAP 一、介绍 Kerberos是一种计算机网络授权协议&#xff0c;主要用于在非安全网络环境中对个人通信进行安全的身份认证。这个协议由麻省理工学院&#xff08;MIT&#xff…

软考-系统分析师-精要1

1、什么是软件需求 软件需求是指用户对系统在功能、行为、性能、设计约束等方面的期望。 软件需求是指用户解决问题或达到目标所需的条件或能力&#xff0c;是系统或系统部件要满足合同、标准、规范或其他正式规定文档所需具有的条件或能力&#xff0c;以及反映这些条件或能力…

Leetcode 118 杨辉三角

目录 一、问题描述二、示例及约束三、代码方法一&#xff1a;数学 四、总结 一、问题描述 给定一个非负整数 numRows&#xff0c;生成「杨辉三角」的前 numRows 行。   在「杨辉三角」中&#xff0c;每个数是它左上方和右上方的数的和。 二、示例及约束 示例 1&#xff1a…

电子防潮柜出厂前要经过哪些测试?

电子防潮柜在发货前应执行一系列质量控制测试以确保其功能正常、性能稳定且能够满足用户存储物品对湿度控制的需求。以下是沐渥电子防潮柜出厂前的测试流程&#xff1a; 1&#xff09;除湿性能测试&#xff1a;检查并验证防潮柜能否按照设定的湿度目标值准确运行&#xff0c;可…

燃冬之yum、vim和你

了解了很多指令和权限&#xff0c;搞点真枪实弹来瞅瞅 学Linux不是天天就在那掰扯指令玩&#xff0c;也不是就研究那个权限 准备好迎接Linux相关工具的使用了么码农桑~ yum 软件包 什么是软件包呢&#xff1f; 首先来举个生活中常见点的例子&#xff1a;比如我的手机是华为…