算法的复杂度

1.数据结构前言

下面的概念有的比较难理解,做个了结就行。

1.1数据结构的起源

在现实生活中我们更多地并不是解决数值计算的问题,而是 需要一些更科学的手段如(表,数,图等数据结构),才能更好地处理问题。所以数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及他们之间的关系和操作等相关问题的学科。

1968年,美国高德纳教授在其所写的《计算机程序设计艺术》第一卷《基本算法》中,较系统的阐述了数据的逻辑结构及其操作。

1.2数据结构(Data Structure)的定义

数据结构:相互之间存在一种或者多种关系的数据元素的集合

数据元素:是组成数据的,有一定意义的基本单位,在计算机中被当做成体处理。也叫做记录。比如在人类社会中,它的数据元素就是人。畜类中,牛羊猪等就是它的数据元素。

数据项:一个数据元素可以由多个数据项组成。比如人的数据项可以由眼睛、鼻子、嘴巴等等。

数据对象:具有相同性质的数据元素的集合,是数据的子集。比如人都有生日、姓名、性别,把这些拥有相同数据项的数据元素就称为相同性质的数据元素。

1.3逻辑结构与物理结构

1.3.1逻辑结构

逻辑结构:数据元素之间的相互关系。

常见的逻辑结构:

集合结构:(”平等“)

线性结构:(一对一)

树形结构:(一对多)

图形结构:(多对多)

1.3.2物理结构

物理结构:指的是数据的逻辑结构在计算机中的存储方式

存储结构的分类:顺序存储结构、链式存储结构

顺序存储结构:把数据元素存放在连续的内存空间中,这种的结构的物理结构与逻辑结构是相同的

链式存储结构:把数据元素存放在任意的内存空间中,这个任意可以连续也可以不连续。

这种存储结构的操作是建立在指针域上的,因为你总得通过一个手段去找到这些元素。

1.4抽象数据类型

1.4.1数据类型

数据类型:只一组具有相同性质的的集合以及定义在此集合上面的一组操作的总称。

高级语言中,类型往往指代的是变量、常量、表达式所能表示的范围,还有所能进行的+ - * /等一系列操作。

在C语言中,数据类型分为:

原子类型:不可再分的基本单位,包括整形、浮点型、字符型

结构类型:由若干个类型组合而成,可以再分。比如:一个整形数组就包含若干个整形数据。

1.4.2抽象数据类型

抽象是指抽出事物具有的本质属性

抽象数据类型:是指一个数学模型以及定义在该模型上面的一组操作。

对于抽象数据类型,我们并不关注数据本身的物理结构,而是关注它的数学抽象特征。

一个抽象数据类型定义了:一个数据对象、数据元素中各数据元素之间的关系及对数据的操作。

2.算法的复杂度

在次之前我们先看一个例题:189. 轮转数组 - 力扣(LeetCode)

经过考虑我们可以有三种解法:

1.挨个轮转

void rotate(int* nums, int numsSize, int k) {int i=0;while(k--){int tmp=nums[numsSize-1];for(i=numsSize-1;i>0;i--){nums[i]=nums[i-1];}nums[0]=tmp;}
}

2.取余挨个轮转:

void rotate(int* nums, int numsSize, int k) {int i=0;k%=numsSize;while(k--){int tmp=nums[numsSize-1];for(i=numsSize-1;i>0;i--){nums[i]=nums[i-1];}nums[0]=tmp;}
}

3.面向结果编程:

void rotate(int* nums, int numsSize, int k) {int ans[numsSize];int i=0;for(i=0;i<numsSize;i++){ans[(i+k)%numsSize]=nums[i];}for(i=0;i<numsSize;i++){nums[i]=ans[i];}}

4.三次逆序法:

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

2.1时间复杂度

先说明一下:上述方法的1、2的关系为优化。3、4是使用了不同的算法。

2.1.1时间复杂度的定义

时间复杂度:在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)数量级。算法的时间复杂度,也就是算法的时间量度,记作T(n)=O(f(n))。它表示随着问题规模n的增大,算法的执行时间的增长率和符f(n)的增长率相同,称作算法的渐进时间复杂度,简称时间复杂度。其中符f(n)是问题规模n的某个函数。

这里我们从定义中提取几个关键点:

1.算法时间复杂度是算法渐进时间复杂度的简称。

2.它表示的是一种变化趋势(随问题规模)或者增长率。

3.并不是一个确切的语句到底执行多少次的函数表达式。

2.1.2算法时间复杂度的大O渐进表示法

大O符号(Big O notation):是用于描述函数渐进行为的数学符号
💡 推导⼤O阶规则
1. 时间复杂度函数式 T(N) 中,只保留最⾼阶项,去掉那些低阶项,因为当 N 不断变大时,
低阶项对结果影响越来越小,当 N 无穷大时,就可以忽略不计了。
2. 如果最高阶项存在且不是 1 ,则去除这个项目的常数系数,因为当 N 不断变大,这个系数
对结果影响越来越小,当 N 无穷大时,就可以忽略不计了。
3. T(N) 中如果没有 N 相关的项目,只有常数项,用常数 1 取代所有加法常数。

2.1.3算法时间复杂度的例题:

2.1.3.1
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}

T(n)=2*n+10(只关注循环的额外开销)

时间复杂度:O(n)

2.1.3.2
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{
++count;
}
for (int k = 0; k < N ; ++
k)
{
++count;
}
printf("%d\n", count);
}

同样的时间复杂度:O(n)

2.1.3.3
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}

O(1)

2.1.3.4
const char * strchr ( const char
* str, int character)
{
const char* p_begin = s;
while (*p_begin != character)
{
if (*p_begin == '\0')
return NULL;
p_begin++;
}
return p_begin;
}

这是一个查找某个字符的算法,但是不同情况有不同的复杂度有不同划分:

假设要找的就在第一个字符位置(或常数个):T(n)=k(常数) --> O(1)4

假设要找的在最后一个位置:T(n)=n --> O (n)

假设要找的在中间:T(n)=n/2 --> O(n)

2.1.3.5
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}

T(n)=N*(N+1)/2 -->O(n)=n^2

2.1.3.6
void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}

O(n)=logn  这里写成lnn lgn都行,因为我们说时间复杂度表示的是变化率,所以只需要表示出来对数阶就可以。

2.1.3.7

递归的时间复杂度

// 计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}

O(n)=n

递归时间复杂度的求法=单次递归的时间复杂度*递归次数

2.1.4常见的时间复杂度

2.2.空间复杂度

空间复杂度也是⼀个数学表达式,是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占⽤了多少bytes的空间,因为常规情况每个对象大小差异不会很大,所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐进表示法
注意:函数运行时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定
当不加限定的说复杂度时一般指代的是时间复杂度,所以空间复杂度的讨论并不会很深入。
例题:
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}

由于额外开辟的空间仅是几个常量所以空间复杂度为O(1)

3.轮转数组复杂度分析

法一:O(n^2)    O(1)

法二:O(n^2)    O(1)

法三:O(n)       O(n)

法四:O(n)       O(1)

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

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

相关文章

#渗透测试#红蓝攻防#HW#漏洞挖掘#漏洞复现01-笑脸漏洞(vsftpd)

免责声明 本教程仅为合法的教学目的而准备&#xff0c;严禁用于任何形式的违法犯罪活动及其他商业行为&#xff0c;在使用本教程前&#xff0c;您应确保该行为符合当地的法律法规&#xff0c;继续阅读即表示您需自行承担所有操作的后果&#xff0c;如有异议&#xff0c;请立即停…

matlab2024a安装

1.开始安装 2.点击安装 3.选择安装密钥 4.接受条款 5.安装密钥 21471-07182-41807-00726-32378-34241-61866-60308-44209-03650-51035-48216-24734-36781-57695-35731-64525-44540-57877-31100-06573-50736-60034-42697-39512-63953 6 7.选择许可证文件 8.找许可证文件 9.选…

第二节——计算机网络(四)物理层

车载以太网采用差分双绞线车载以太网并未指定特定的连接器&#xff0c;连接方式更为灵活小巧&#xff0c;能够大大减轻线束重量。传统以太网一般使用RJ45连接器连接。车载以太网物理层需满足车载环境下更为严格的EMC要求&#xff0c;100BASE-T1\1000BASE-T1对于非屏蔽双绞线的传…

电脑还原重置Windows系统不同操作模式

电脑有问题,遇事不决就重启,一切都不是问题!是真的这样吗。其实不然,主机系统重启确实可以自动修复一些文件错误,或者是设置问题,但是,当你由于安装了错误的驱动或者中毒严重,亦或是蓝屏,那么重启这个方子可能就治不了你的电脑了。 那么,除了当主机出现异常故障现象…

Lumos学习王佩丰Excel第十八讲:LOOKUP函数与数组

一、回顾统计函数 1、使用SUMIF函数 sumif(条件区域,求和条件,求和区域) 2、使用SUMIFS函数 SUMIFS(求和范围, 条件范围1, 条件1, 条件范围2, 条件2, ...) 二、认识数组 1、数组生成原理 所谓数组&#xff0c;是有序的元素序列。组成数组的各个变量称为数组的元素。对于Ex…

JVM知识点学习-1

学习视频&#xff1a;狂神说Java 类加载器和双亲委派机制 类加载器 作用&#xff1a;加载Class文件 流程&#xff1a;这里的名字car1。。在栈里面&#xff0c;但是数据在堆里面 类加载器的几个类型&#xff1a; 虚拟机自带的类加载器&#xff1b;启动类&#xff08;根Boot…

Spring源码的分析之启动流程

一.前言 这篇文章的话就是我个人通过一些技术博客以及自己写一些Demo测试获得的一些感悟但是 由于本人的技术水平有限所以肯定就是会出现一些问题所以希望看这篇文章的时候如果发现错误的时候可以提出来然后我个人的话进行修改 二.SpringApplication 的构造函数 创建的一个简单…

Scala学习记录,全文单词统计

package test32 import java.io.PrintWriter import scala.io.Source //知识点 // 字符串.split("分隔符"&#xff1a;把字符串用指定的分隔符&#xff0c;拆分成多个部分&#xff0c;保存在数组中) object test {def main(args: Array[String]): Unit {//从文件1.t…

Linux下的三种 IO 复用

目录 一、Select 1、函数 API 2、使用限制 3、使用 Demo 二、Poll 三、epoll 0、 实现原理 1、函数 API 2、简单代码模板 3、LT/ET 使用过程 &#xff08;1&#xff09;LT 水平触发 &#xff08;2&#xff09;ET边沿触发 4、使用 Demo 四、参考链接 一、Select 在…

LeetCode 3208.交替组 II:滑动窗口

【LetMeFly】3208.交替组 II&#xff1a;滑动窗口 力扣题目链接&#xff1a;https://leetcode.cn/problems/alternating-groups-ii/ 给你一个整数数组 colors 和一个整数 k &#xff0c;colors表示一个由红色和蓝色瓷砖组成的环&#xff0c;第 i 块瓷砖的颜色为 colors[i] &a…

与7无关的数

与7无关的数 C语言代码C 语言代码Java语言代码Python语言代码 &#x1f490;The Begin&#x1f490;点点关注&#xff0c;收藏不迷路&#x1f490; 一个正整数&#xff0c;如果它能被7整除,或者它的十进制表示法中某一位上的数字为7&#xff0c;则称其为与7相关的数。现求所有小…

07.ES11 08.ES12

7.1、Promise.allSettled 调用 allsettled 方法&#xff0c;返回的结果始终是成功的&#xff0c;返回的是promise结果值 <script>//声明两个promise对象const p1 new Promise((resolve, reject) > {setTimeout(() > {resolve("商品数据 - 1");}, 1000)…

git 上传代码时报错

在上传代码时&#xff0c;显示无法上传 PS E:\JavaWeb\vue3-project> git push To https://gitee.com/evening-breeze-2003/vue3.git! [rejected] master -> master (non-fast-forward) error: failed to push some refs to https://gitee.com/evening-breeze-20…

视觉语言模型(VLM)学习笔记

目录 应用场景举例 VLM 的总体架构包括&#xff1a; 深度解析&#xff1a;图像编码器的实现 图像编码器&#xff1a;视觉 Transformer 注意力机制 视觉-语言投影器 综合实现 训练及注意事项 总结 应用场景举例 基于文本的图像生成或编辑&#xff1a;你输入 “生成一张…

digit_eye开发记录(3): C语言读取MNIST数据集

在前两篇&#xff0c;我们解读了 MNIST 数据集的 IDX 文件格式&#xff0c;并分别用 C 和 Python 做了 读取 MNIST 数据集的实现。 基于 C 的代码稍长&#xff0c;基于 Python 的代码则明显更短&#xff0c;然而它们的共同特点是&#xff1a;依赖了外部库&#xff1a; 基于 C …

C#窗体小程序计算器

使其能完成2个数的加、减、乘、除基本运算。界面如下图&#xff0c;单击相应的运算符按钮&#xff0c;则完成相应的运算&#xff0c;并将结果显示出来&#xff0c;同时不允许在结果栏中输入内容 代码如下&#xff1a; private void button1_Click(object sender, EventArgs e)…

Linux命令进阶·如何切换root以及回退、sudo命令、用户/用户组管理,以及解决创建用户不显示问题和Ubuntu不显示用户名只显示“$“符号问题

目录 1. root用户&#xff08;超级管理员&#xff09; 1.1 用于账户切换的系统命令——su 1.2 退回上一个用户命令——exit 1.3 普通命令临时授权root身份执行——sudo 1.3.1 为普通用户配置sudo认证 2. 用户/用户组管理 2.1 用户组管理 2.2 用户管理 2.2.1 …

【JavaEE】JavaEE、web 开发、框架(Spring) 、Maven

文章目录 一、JavaEE 发展历程二、什么是 web 开发1、什么是 web 开发&#xff1f;2、web 网站的工作流程 三、框架1、什么是框架&#xff1f;2、为什么要学框架&#xff1f;3、框架的优点&#xff08;Spring Boot VS Servlet&#xff09; 四、Maven 一、JavaEE 发展历程 Java…

虚拟机玩游戏,轻松实现多开不同IP

嘿&#xff0c;亲爱的游戏小伙伴们&#xff01;今天要和大家分享一个超级实用的技巧&#xff0c;让你在游戏中轻松多开不同IP&#xff0c;享受开挂的乐趣&#xff01; 第一步&#xff1a;准备虚拟机 首先&#xff0c;你需要下载一个虚拟机软件&#xff0c;比如VMware或者Virt…

MySQL常用语句整理

《SQL必知必会》(第3版)SQL是目前使用最为广泛的数据库语言之一。本书没有涉及理论&#xff0c;而是从实践出发&#xff0c;由浅入深地讲解了广大读者所必需的SQL知识&#xff0c;适用于各种主流数据库。实例丰富&#xff0c;便于查阅。本书涉及不同平台上数据的排序、过滤和分…