NO.42十六届蓝桥杯备战|数据结构|算法|时间复杂度|空间复杂度|STL(C++)

数据结构

什么是数据结构

在计算机科学中,数据结构是⼀种数据组织、管理和存储的格式。它是相互之间存在⼀种或多种特定关系的数据元素的集合。
说点通俗易懂的话,数据结构就是数据的组织形式,研究的就是把数据按照何种形式存储在计算机中

为什么会有数据结构
  • 随着计算机的发展和应⽤范围的拓展,计算机需要处理的数据量越来越⼤,数据类型越来越多,数据之间的关系也越来越复杂。
  • 这就要求⼈们对计算机加⼯处理的数据进⾏系统的研究,即研究数据的特性、数据之间存在的关系,以及如何有效的组织、管理存储数据,从⽽提⾼计算机处理数据的效率。
  • 数据结构这⻔学科就是在此背景上逐渐形成和发展起来的。
    对数据结构更深层次的理解:数据结构研究的是数据本⾝的特性、数据与数据之间的关系,以及如何在计算机中存储数据,从⽽⾼效的处理这些数据。

数据结构的三要素

逻辑结构

逻辑结构:数据中各元素之间的逻辑关系。
它只关⼼数据中各个元素之间的关系,并不关⼼数据是怎么在内存中存储的

常⻅的逻辑结构

  1. 集合
    所有的数据只是在⼀个集合中,彼此之间再没有其他的联系
  2. 线性结构
    数据之间只存在⼀对⼀的关系
  3. 树形结构
    数据之间是⼀对多的关系
  4. 图结构
    数据之间存在多对多的关系
存储结构

存储结构⼜称物理结构,但是存储⼆字更能体现本意,后续我们统称存储结构。
存储结构顾名思义,就是数据在计算机中是如何存储的。
⽤⼤⽩话就是,怎么把这个数据结构存到计算机中。
数据的存储结构主要有顺序存储以及链式存储。

  1. 顺序存储
    把逻辑上相邻的元素存储在物理上也相邻的存储单元中。-数组
    在程序中典型处理⽅式即数组。即数据不仅在逻辑上是连续的,物理上也是连续的
  2. 链式结构
    通过指针来存储前⼀个或下⼀个数据元素的地址,从⽽实现元素和元素之间的关系
数据的运算

数据的运算(针对数据的各种操作),包括数据结构的实现,以及基于数据结构上的各种操作

  • 创建数据结构;
  • 增加数据;
  • 删除数据;
  • 查找数据;
  • 修改数据;
  • 排序数据;
  • 输出数据;

算法

什么是算法

算法(Algorithm)是指解题⽅案的准确⽽完整的描述,是⼀系列解决问题的清晰指令,算法代表着⽤系统的⽅法描述解决问题的策略机制。也就是说,能够对⼀定规范的输⼊,在有限时间内获得所要求的输出。

  • 算法是可以没有输⼊的,⼀定要有输出的。没有输出的算法是没有意义的。
    简单来说算法就是⼀系列的步骤,⽤来将输⼊数据转化成输出结果
算法好坏的度量

【事前分析法】
算法设计好后,根据算法的设计原理,只要问题规模确定,算法中基本语句执⾏次数和需求资源个数基本也就确定了

算法执⾏所需资源的个数与问题规模n有关。因此可以根据算法执⾏过程中对空间的消耗来衡量算法的好坏,这就是空间复杂度
算法中基本语句总的执⾏次数与问题规模n有关。因此可以根据算法执⾏过程中,所有语句被执⾏的次数之和来衡量算法的好坏,这就是时间复杂度。
综上所述,时间和空间的消耗情况就是我们度量⼀个算法好坏的标准,也就是时间复杂度和空间复杂度

时间复杂度

在计算机科学中,算法的时间复杂度是⼀个函数式 T ( N ) T(N) T(N) ,它定量描述了该算法的运⾏时间。这个函数式 T ( N ) T(N) T(N)计算了程序中语句的执⾏次数

计算⼀下fun中++count语句总共执⾏了多少次

void fun(int N)  
{  int count = 0;  for(int i = 0; i < N; i++)  {  for(int j = 0; j < N; j++)  {  ++count; // 执⾏次数是 n*n,也就是 n^2  }  }  for(int k = 0; k < 2 * N; k++)  {  ++count; // 执⾏次数是 2*n  }  int M = 10;  while(M--)  {  ++count; // 执⾏次数 10  }  
}

fun 函数 ++count 语句的总执⾏次数:
T (N) = N^2 + 2 × N + 10

  • 当N = 10 时,T (N) = 100 + 20 + 10 = 130
  • 当N = 100 时,T (N) = 10000 + 200 + 10 = 10210
  • 当N = 1000 时,T (N) = 1000000 + 2000 + 10 = 1002010
  • 当N = 10000 时,T (N) = 100000000 + 20000 + 10 = 100020010
⼤O表⽰法

在上述案例中,对N取值进⾏分析,随着N的增⼤,对结果影响最⼤的⼀项是N^2 ,2xN和10可以忽略不计,算法执⾏时间的增⻓率与 T ( N ) T(N) T(N)中的N^2的增⻓率基本⼀致。
因此,在计算时间复杂度的时候,⼀般会把 T ( N ) T(N) T(N)中对结果影响不⼤的项忽略掉,该种表⽰时间复杂度的⽅式称为⼤O渐进时间复杂度-粗略的估计⽅式,只看影响时间开销最⼤的⼀项。
所以对于上述fun函数,其时间复杂度为 O ( T ( N ) ) = O ( N 2 + 2 N + 10 ) O(T(N))=O(N^2+2N+10) O(T(N))=O(N2+2N+10),取最⾼阶项最终为: O ( N 2 ) O(N^2) O(N2)

推导⼤O渐进时间复杂度的规则

  1. 时间复杂度函数式T (N)中,只保留最⾼阶项,去掉那些低阶项;
  2. 如果最⾼阶项存在且不是1 ,则去除这个项⽬的常数系数;
  3. T (N) 中如果没有N 相关的项⽬,只有常数项,⽤常数1 取代所有加法常数。
最优、平均和最差时间复杂度

在n 个整形元素数组中,检测x 是否存在,若存在返回其在数组中的下标,否则返回-1

int find (int a[], int n, int x)  
{  for (int i = 0; i < n; i++){  if (a[i] == x)  return i;  }  return -1;  
}

![[Pasted image 20250315162034.png]]

21156634829553784617
0123456789

在查找过程中,需⽤x 与数组中元素依次⽐较,因此总的⽐较次数就是该算法的时间复杂度。则:

  • 若待查找元素x 为21 ,只需要⽐较1 次,为算法的最优(好)情况。
  • 若带查找元素x 为17 ,或者是不存在的元素,需要⽐较n 次,为算法的最坏(差)情况。
  • 所有情况的⽐较次数之和,除以总情况,为算法的平均情况。
    查找第⼀个元素需⽐较1次,查找第2个元素需⽐较2次,…,查找第n个元素需⽐较n次,假设每个元素查找的概率相同,则平均⽐较次数为
    f ( n ) = 1 + 2 + 3 + ⋯ + n n = ( 1 + n ) × n 2 n = 1 + n n f(n)=\frac{1+2+3+\dots+n}{n}=\frac{(1+n)\times n}{2n}=\frac{1+n}{n} f(n)=n1+2+3++n=2n(1+n)×n=n1+n
  • 最好时间复杂度为O(1) ;
  • 最坏时间复杂度为O(n) ;
  • 平均时间复杂度为 O ( 1 + n 2 ) O(\frac{1+n}{2}) O(21+n) ,也就是 O ( n ) O(n) O(n)
    但是,⽆论是在竞赛还是⼯程中,算法的时间复杂度⼀般为最差情况。因为最差情况是⼈对⼀件事情所能承受的底线,因此find 算法的时间复杂度为O(n) 。

时间复杂度计算案例

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

基本语句 ++count 关于问题规模n总执⾏次数的数学表达式为:f(n) = n × 2 + 10 ;
保留最⾼阶项,省略最⾼阶项的系数后的⼤O渐进表⽰法为:O(n)

案例⼆
void func2(int N)  
{  int count = 0;  for (int k = 0; k < 1000; k++)  {  ++count;  }  printf("%d\n", count);  
}

基本语句 ++count 关于问题规模n总执⾏次数的数学表达式为:f(n) = 1000 ;
不论n如何变化, ++count 总的执⾏次数都是1000 ,故时间复杂度为:O(1)

案例三
void func3(int m, int n)  
{for (int i = 0; i < m; i++)  {  printf("hello\n");  }  for (int i = 0; i < n; i++)  {  printf("hello\n");  }  
}

基本语句 printf(“”) 总的执⾏次数为f(m, n) = m + n ;
m和n的变化都是影响基本语句执⾏次数,即m和n都是问题规模,故时间复杂度为 O ( m , n ) O(m,n) O(m,n) ,或者也可以表⽰为 O ( m a x ( m , n ) ) O(max(m, n)) O(max(m,n))

案例四
void func4(int m, int n)  
{  for (int i = 0; i < m; i++)  {  for(int j = 0; j < n; j++)  {  printf("%d, ", i);  }  printf("\n");  }  
}

基本语句 printf("%d, ", i) 总的执⾏次数为f(m, n) = m × n ;
m和n的变化都是影响基本语句执⾏次数,即m和n都是问题规模,故时间复杂度为 O ( m × n ) O(m \times n) O(m×n)

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

假设执⾏次数为x ,则 2 x = n 2^x=n 2x=n ;因此执⾏次数: x = log ⁡ 2 n x=\log_{2}n x=log2n
⼀般情况下不管底数是多少都可以省略不写,那么本案例的时间复杂度为 log ⁡ n \log n logn

案例六
// ⽤递归计算 N 的阶乘  
long long fac(int N)  
{  if(N == 0) return 1;  return fac(N - 1) * N;  
}

递归算法时间复杂度求解⽅式为,单次递归时间x总的递归次数。
注意,这⾥只是简易的估算⽅式。递归算法的时间复杂度严谨的计算⽅法是利⽤主定理(Master
Theorem)来求得递归算法的时间复杂度。
对于递归算法,仅需掌握这样简易的计算⽅式

单次递归没有循环之类,所以时间复杂度为常数。总的递归次数就是递归过程中,fac递归调⽤了多少次。
Fac(5) 需要递归6次,则Fac(n) 就需要递归n + 1次,故递归求阶乘的时间复杂度为O(n) 。

空间复杂度

有了时间复杂度的铺垫,空间复杂度的计算就⽐较容易了。
在算法竞赛中,空间复杂度就是整个程序在解决这个问题时,⼀共使⽤了多少空间。相⽐较于时间复杂度,空间复杂度就没那么受关注,因为多数情况下题⽬所给的内存限制是⾮常宽裕的。
但是,这并不表明可以肆⽆忌惮的使⽤空间,⼀旦超出给定的限制,程序也是不会通过的

冒泡排序
#include <iostream>  
using namespace std;  
const int N = 20;  
int arr[N];  
int main()  
{  int n = 0;  cin >> n;  int i = 0;  //输⼊  for(i=0; i < n; i++)  cin >> arr[i];  //排序  for(i = 0; i < n-1; i++)  {  int j = 0;  for(j = 0; j <= n-1-i; j++)  {  if(arr[j] < arr[j+1])  {  int tmp = arr[j];  arr[j] = arr[j+1];  arr[j+1] = tmp;  }  }  }  //输出  for(i=0; i < n; i++)  {  cout << arr[i] << endl;  }  return 0;  
}

空间复杂度:需要⼀个和问题规模⼀致的数组来存数据。因此空间复杂度为O(N)

递归求阶乘

递归算法空间复杂度求解⽅式,单次递归空间复杂度*递归次数。

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

递归的调⽤会有空间消耗

常⻅复杂度的增⻓对⽐

各种常⻅的时间复杂度的⼤⼩对⽐:
O ( 1 ) < O ( l o g N ) < O ( N ) < O ( N l o g N ) < O ( N 2 ) < O ( N 3 ) < O ( 2 N ) < O ( n ! ) O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(N^3) < O(2^N ) < O(n!) O(1)<O(logN)<O(N)<O(NlogN)<O(N2)<O(N3)<O(2N)<O(n!)

算法竞赛中的时间限制和空间限制

  1. 信息学竞赛中,C++通常设定1到2秒的时间限制,要控制运⾏次数在107⾄108 之间。
  2. 空间限制在128MB或256MB ,可以开⼀个 3 × 1 0 7 3 \times 10^7 3×107⼤⼩的int类型数组,或者5000x5000⼤⼩的⼆维数组,⼀般情况下都是够⽤的

各种数据量下,可选⽤的算法的时间复杂度

O ( log ⁡ n ) O(\log n) O(logn) O ( n ) O(\sqrt{n}) O(n ) O ( n ) O(n) O(n) O ( n ∗ log ⁡ n ) O(n*\log n) O(nlogn) O ( n 2 ) O(n^2) O(n2) O ( n 3 ) O(n^3) O(n3) O ( 2 n ) O(2^n) O(2n) O ( n ! ) O(n!) O(n!)
n ≤ 10 n\le 10 n10
n ≤ 25 n \le 25 n25×
n ≤ 100 n\le 100 n100××
n ≤ 1 0 3 n \le 10^3 n103×××
n ≤ 2 ∗ 1 0 5 n \le 2*10^5 n2105××××
n ≤ 1 0 7 n \le 10^7 n107×××××
n ≤ 1 0 9 n \le 10^9 n109××××××
n ≤ 1 0 18 n \le 10^{18} n1018×××××××

STL

C++标准库

C++标准是C++编程语⾔的规范,由国际标准化组织(ISO)制定。C++标准的发展历程可以追溯到1998年,当时ISO/IEC14882:1998标准被发布,这是第⼀个C++标准,常被称为C++98。随后,C++标准经历了多次更新和修订,包括C++03(2003年)、C++11(2011年)、C++14(2014年)、C++17(2017年)以及C++20。
最新的C++标准是C++23,于2023年发布,引⼊了许多新特性,但⽬前⽀持完整的编译器较少。
每⼀个版本的C++标准不仅规定了C++的语法、语⾔特性,还规定了⼀套C++内置库的实现规范,这个库便是C++标准库。C++标准库中包含⼤量常⽤代码的实现,如输⼊输出、基本数据结构、内存管理、多线程⽀持等。
我们可以这样简单的理解,C++给我们提供了⼀⼤堆的代码,这些代码⾥⾯包含特别多已经实现好的数据结构和算法。因此,在做题的时候,如果涉及的数据结构和算法C++标准库已经帮我们实现好了,那么就可以直接使⽤,避免重复造轮⼦。
造轮⼦指的是重复发明已有的算法,或者重复编写现成优化过的代码。
造轮⼦通常耗时耗⼒,同时效果还没有别⼈好。但若是为了学习或者练习,造轮⼦则是必要的。 因此,学好C++标准库能极⼤的提⾼编程效率

什么是STL

STL即标准模板库(Standard Template Library),是C++标准库的⼀部分,⾥⾯包含了⼀些模板化的通⽤的数据结构和算法。由于其模板化的特点,它能够兼容⾃定义的数据类型,避免⼤量的造轮⼦⼯作。
NOI和ICPC赛事都⽀持STL库的使⽤,当然,蓝桥杯也是⽀持的。因此,⼀定要学习STL的使⽤,能够极⼤的提⾼编写代码的效率

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

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

相关文章

【CSS3】化神篇

目录 平面转换平移旋转改变旋转原点多重转换缩放倾斜 渐变线性渐变径向渐变 空间转换平移视距旋转立体呈现缩放 动画使现步骤animation 复合属性animation 属性拆分逐帧动画多组动画 平面转换 作用&#xff1a;为元素添加动态效果&#xff0c;一般与过渡配合使用 概念&#x…

Keepalived高可用架构实战:从安装配置到高级应用详解

一.架构 用户空间核心组件&#xff1a; vrrp stack&#xff1a;VIP 消息通信checkers&#xff1a;监测 Real Serversystem call&#xff1a;实现 vrrp 协议状态转换时调用相关本地功能SMTP&#xff1a;邮件组件IPVS wrapper&#xff1a;生成 IPVS 规则Netlink Reflector&…

Linux:利用System V系列的-共享内存,消息队列实现进程间通信

对于管道的进程间通信方式&#xff0c;需要频繁的调用系统调用(read,write)。而我们今天首先要介绍的共享内存&#xff0c;在开辟好空间之后&#xff0c;便可以跳过系统调用&#xff0c;直接进行读写操作。 一.System V共享内存(主要) 共享内存区是最快的IPC形式。一旦这样的内…

不像人做的题————十四届蓝桥杯省赛真题解析(上)A,B,C,D题解析

题目A&#xff1a;日期统计 思路分析&#xff1a; 本题的题目比较繁琐&#xff0c;我们采用暴力加DFS剪枝的方式去做&#xff0c;我们在DFS中按照8位日期的每一个位的要求进行初步剪枝找出所有的八位子串&#xff0c;但是还是会存在19月的情况&#xff0c;为此还需要在CHECK函数…

宇树人形机器人开源模型

1. 下载源码 https://github.com/unitreerobotics/unitree_ros.git2. 启动Gazebo roslaunch h1_description gazebo.launch3. 仿真效果 H1 GO2 B2 Laikago Z1 4. VMware: vmw_ioctl_command error Invalid argument 这个错误通常出现在虚拟机环境中运行需要OpenGL支持的应用…

【C/C++算法】从浅到深学习--- 前缀和算法(图文兼备 + 源码详解)

绪论&#xff1a;冲击蓝桥杯一起加油&#xff01;&#xff01; 每日激励&#xff1a;“不设限和自我肯定的心态&#xff1a;I can do all things。 — Stephen Curry” 绪论​&#xff1a; 本章将使用八道题由浅到深的带你了解并基本掌握前缀和思想&#xff0c;以及前缀和的基…

脑电:时域分析(任务态)

时域分析&#xff1a;时间序列&#xff08;时域信号&#xff09; EEG和ERP都是时间序列 ERP&#xff1a;事件诱发的电位是随着时间变化 组水平&#xff1a;需要这一组的个体不能差异性太大。 提值的指标&#xff0c;选取平均幅值确定成分的显著情况 mean(EEG.data,3): 在第…

【C语言】自定义类型:结构体,联合,枚举(下)

前言&#xff1b;上一期我们侧重讲了一个非常重要的自定义类型结构体&#xff0c;这一期我们来说说另外两种自定义类型&#xff1a;联合&#xff0c;和枚举。 传送门&#xff1a;自定义类型&#xff1a;结构体&#xff0c;联合&#xff0c;枚举(上) 文章目录 一&#xff0c;联…

数组的介绍

1.数组的概念 数组是一组相同类型元素的集合&#xff0c;从这个描述中我们知道&#xff1a; 数组中存放1个或多个数据&#xff0c;但是数组的元素个数不为0。数组中存放的多个数据&#xff0c;类型是相同的。 数组分为一维数组和多维数组&#xff0c;多维数组一般比较多见的…

蓝桥杯 17110抓娃娃

问题描述 小明拿了 n 条线段练习抓娃娃。他将所有线段铺在数轴上&#xff0c;第 i 条线段的左端点在 li&#xff0c;右端点在 ri​。小明用 m 个区间去框这些线段&#xff0c;第 i个区间的范围是 [Li​, Ri​]。如果一个线段有 至少一半 的长度被包含在某个区间内&#xff0c;…

linux ptrace 图文详解(二) PTRACE_TRACEME 跟踪程序

目录 一、基础介绍 二、PTRACE_TRACE 实现原理 三、代码实现 四、总结 &#xff08;代码&#xff1a;linux 6.3.1&#xff0c;架构&#xff1a;arm64&#xff09; One look is worth a thousand words. —— Tess Flanders 一、基础介绍 GDB&#xff08;GNU Debugger&…

记录致远OA服务器硬盘升级过程

前言 日常使用中OA系统突然卡死&#xff0c;刷新访问进不去系统&#xff0c;ping服务器地址正常&#xff0c;立马登录服务器检查&#xff0c;一看磁盘爆了。 我大脑直接萎缩了&#xff0c;谁家OA系统配400G的空间啊&#xff0c;过我手的服务器没有50也是30台&#xff0c;还是…

电网电压暂态扰动机理与工业设备抗失压防护策略研究

什么是晃电&#xff1f; 国标GB/T 30137-2013 中定义:工频电压方均根值突然降至额定值的90%~10%&#xff0c;持续时间为10ms~1min后恢复正常的现象。Acrel8757V 晃电的原因 1.系统侧因素 短路故障&#xff1a;雷击、线路接地、设备误碰等导致电网短路&#xff0c;故障点电压…

Linux监控网络状态

一、基本介绍 1、基本语法 netstat [选项] 2、常用选项 选项 说明 -a 显示所有连接和监听的套接字&#xff08;包括TCP、UDP&#xff09;。 -t 显示 TCP 连接。 -u 显示 UDP 连接。 -l 显示正在监听的套接字&#xff08;server端&#xff09;。 -n 显示数字格式的…

UE5以插件的形式加载第三方库

之前在UE中加载第三方库的形式是以静态或者动态链接的形式加载但是不太容易复用。就想着能不能以插件的形式加载第三方库&#xff0c;这样直接把插件打包发行就可以复用了&#xff0c;之前也找过相应的教程但是很难找到比较简单易懂的教程&#xff0c;要么是比较复杂&#xff0…

Go执行当前package下的所有方法

需求&#xff1a;需要一个文件一个定时任务方法&#xff0c;当项目初始化完毕后&#xff0c;自动加载并执行这些定时任务方法 项目目录架构 main.go 初始化 package mainimport ("sql_demo/schedule" )func main() {/***** 其他初始化完毕后的操作**/// 定时任务sc…

AnyAnomaly: 基于大型视觉语言模型的零样本可定制视频异常检测

文章目录 速览摘要1. 引言2. 相关工作视频异常检测大型视觉语言模型&#xff08;LVLMs&#xff09; 3. 方法3.1. 总览3.2. 关键帧选择模块3.3. 上下文生成基于 WinCLIP 的注意力机制网格图像生成 3.4. 异常检测提示词设计异常评分 4. 实验4.1. 数据集4.2. 评估标准4.3. 结果4.4…

【AWS入门】2025 AWS亚马逊云科技账户注册指南

【AWS入门】2025 AWS亚马逊云科技账户注册指南 A Guide To Register a New account on AWS By JacksonML 0. AWS亚马逊云科技简介 Amazon Web Service(AWS) 即亚马逊云科技&#xff0c;其在全球Cloud Computing(云计算)市场占有最为重要的地位。 AWS连续13年被Gartner评为…

Spring 中 SmartInitializingSingleton 的作用和示例

一、 接口定义 SmartInitializingSingleton 是 Spring 框架提供的一个 单例 Bean 全局初始化回调接口&#xff0c;用于在 所有非延迟单例 Bean 初始化完成后 执行自定义逻辑。 核心方法&#xff1a; public interface SmartInitializingSingleton {void afterSingletonsInsta…

element tree树形结构默认展开全部

背景&#xff1a; el-tree树形结构&#xff0c;默认展开全部&#xff0c;使用属性default-expand-all【是否默认展开所有节点】&#xff1b;默认展开一级&#xff0c;设置default-expanded-keys【默认展开的节点的 key 的数组】属性值为数组。 因为我这里的数据第一级是四川【省…