网站推广seo方法,浏览器编程语言,个人域名备案需要哪些资料,中石油网站建设一、数据结构
1.1 什么是数据结构#xff1f; 在计算机科学中#xff0c;数据结构是一种 数据组织、管理和存储的格式。它是相互之间存在一种 或多种特定关系的数据元素的集合。 --- 通俗点#xff0c;数据结构就是数据的组织形式 #xff0c; 研究数据是用什么方…一、数据结构
1.1 什么是数据结构 在计算机科学中数据结构是一种 数据组织、管理和存储的格式。它是相互之间存在一种 或多种特定关系的数据元素的集合。 --- 通俗点数据结构就是数据的组织形式 研究数据是用什么方式存储在存储在gv计算机中的 1.2 为什么会有数据结构 1 随着计算机的发展和应用范围的拓展计算机需要处理的数据量越来越大数据类型越来越多数据之间的关系也越来越复杂。 2这就要求⼈们对计算机加工处理的数据进行系列的研究即研究数据的特性、数据之间存在的关系以及如何有效的组织、管理存储数据 从而提高计算机处理数据的效率。 1.3 数据结构的三要素 1.3.1 逻辑结构
数据结构数据中各元素之间的逻辑关系
他只关心数据中各个元素之间的关系 并不关心数据在内存中存储的
1集合 所有数据只是放在一个集合中 彼此之间再没有其他联系 2线性结构数据之间只存在一对一的关系 3树数据之间是一对多的关系 4图结构数据之间存在多对多的关系 1.3.2 存储结构 存储结构又称 物理结构 但是存储二字 更能理解 后续我们统称为数据结构。 存储结构 顾名思义 就是如何把数据在计算机中存储。 1 顺序存储把逻辑上相邻的元素存储在 物理上也相邻的存储单元中 --- 数组逻辑、物理上都是连续的 2链式存储逻辑上两个元素相邻 但是物理结构上不一定相邻 1.3.3 数据的运算
数据的运算针对数据的各种操作 包括数据结构的实现 以及基于数据结构上的各种操作。
--- 意思是 我们已经知道了一堆数据中 各个元素之间的关系 也知道这堆数据应该在内存中如何存储 。
---- 那么接下来就是写代码 完成我们的需求 二、算法
2.1 什么是算法 简单来说 --- 算法就是一系列的步骤 用来将输入数据转化为输出结果用来解决问题 2.2 算法好坏的度量 算法设计好后根据算法的设计原理只要问题规模确定算法中 基本语句执行次数 和 需求资源个数 基本也就确定了。 比如求 1 2 3 ... ( n − 1) n 可以设计三种算法 算法A 需要 开辟大小为N 的空间 const int N 1e5 10;
int a[N];
int sum(int n)
{// 先把 1 ~ n 存起来for(int i 1; i n; i){a[i] i;}// 循环逐个数字相加int ret 0;for(int i 1; i n; i){ret a[i];}return ret;
} 算法B不需要开辟空间 直接求和 int sum(int n)
{// 循环逐个数字相加int ret 0;for (int i 1; i n; i) {ret i;}return ret;
}
算法执行所需资源的个数与问题的规模 n 有关 。因此可以根据算法执行过程中对空间的消耗来衡量算法的好坏 这就是空间复杂度 。 算法C需要循环 n 次 ret n 语句会执行 n 次 而且随着问题规模的增长 执行次数也会增长 。 int sum(int n)
{int ret 0;// 循环逐个数字相加for (int i 1; i n; i) {ret i;}return ret;
} 算法D 不管问题规模 n 为多少 ( 1 n ) * n / 2 语句只会执行1次。 int sum(int n)
{// 利⽤求和公式return (1 n) * n / 2;
}
算法中基本语句总的执行次数与问题规模 n 有关 。因此可以根据算法执行过程中 所有语句被执行的次数之和来衡量算法的好坏 这就是时间复杂度 。
综上所述 时间和空间的消耗情况就是我们度量一个算法好坏的标准 也就是时间复杂度和空间复杂度 。 2.3 时间复杂度
在计算机中 算法的时间复杂度是一个函数式 TN 他定量描述了该算法的运行时间 。这个TN函数式计算了程序中语句的执行次数 。 计算一下 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}
} 2.3.1 大O表示法 因此在计算时间复杂度的时候一 般会把中对结果影响不大的项忽略掉 这种表示时间复杂度的方式称 为大 O 渐进时间复杂度 - 粗略的估计方式 只看影响时间开销最大的⼀项。 2.3.2 最优、平均和最差时间复杂度 案例在 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;
} 1 在查找过程中 x 与数组中元素依次比较 因此总的比较次数就是该算法的时间复杂度。 --- 若待查找元素 x 为 21 只需要比较 1 次为算法的最优(好)情况。 --- 若带查找元素 x 为 17 或者是不存在的元素需要比较 n 次为算法的最坏(差)情况。 --- 所有情况的比较 次数之和除以总情况为算法的平均情况。 无论是在竞赛还是工程中算法的时间复杂度⼀般为最差情况。 因为最差情况是人对⼀件事情所能承受的底线 因此 find 算法的时间复杂度为 O(n ) 。 2.3.3 时间复杂度计算案例
案例一 案例二 基本语句 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(maxm,n)) 。 案例四 基本语句 printf() 总的执行次数为 f(m, n) m x n m 和 n 的变化都是影响基本语句执行次数 即m 和 n 都是问题规模 故时间复杂度为 O ( m x n ) 案例5
void func5(int n)
{int cnt 1;while (cnt n){cnt * 2;}
} 案例六 递归算法时间复杂度求解方式为单次递归时间 × 总的递归次数。 注意这里只是简易的估算方式。递归算法的时间复杂度严谨的计算方法是 利用主定理 (Master Theorem)来求得递归算法的时间复杂度 。 O( n ) 2.4 空间复杂度 在算法竞赛中空间复杂度就是整个程序在解决这个问题时 ⼀共使用了多少空间。相比较于时间复杂度空间复杂度就没那么受关注因为多数情况下题目所给的内存限制是非常宽裕的。 但是这并不表明可以肆无忌惮的使用空间一旦超出给定的限制程序也是不会通过的。 - MLE 案例一冒泡排序
#include iostream
using namespace std;const int N 20;
int arr[N];int main(){int n 0;cin n;int i 0;//输入 for(i0; 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[j1]){int tmp arr[j];arr[j] arr[j1];arr[j1] tmp; }}} //输出for(i0; i n; i){cout arr[i] endl;}return 0;} 案例二递归求阶乘 2.5 常见复杂度的增长对比 2.6 算法中的时间和空间限制 1. 信息学竞赛中C 通常设定 1 到 2 秒的时间限制运行次数在 10^7 ⾄ 10^8 之间。 2.空间限制在128MB 或 256MB 可以开⼀个3 x 10 ^7 大小的int 类型数组或者5000x5000大小的二维数组⼀般情况下都是够⽤的。 各种数据量下可选用的算法的时间复杂度 三、STL
3.1 C标准库 1 C标准是C编程语言的规范由国际标准化组织ISO制定。C标准的发展历程可以追溯到 1998年当时ISO/IEC 14882:1998标准被发布这是第⼀个C标准常被称为C98。随后C标准经历了多次更新和修订包括C032003年、C112011年、C142014年、C172017年以及 C20。 2最新的C标准是C23于2023年发布引入了许多新特性 但目前完整的编译器较少。 3每⼀个版本的 C 标准不仅规定了 C 的语法、语言特性还规定了⼀套 C 内置库的实现规范这个库便是 C 标准库。C 标准库中包含大量常用代码的实现如输入输出、基本数据结构、内存管理、多线程支持等。 4我们可以这样简单的理解C 给我们提供了一大堆的代码这些代码里面包含特别多已经实现好的 数据结构 和 算法 。 因此在做题的时候如果涉及的数据结构和算法 C 标准库已经帮我们实现好 了那么就可以直接使用避免重复造轮子 。 --- sort / min / max / swap 1 造轮子指的是重复发明已有的算法或者重复编写现成优化过的代码。 2造轮子通常耗时好力同时效果还没有别人好。但若是为了学习或者练习造轮子则是必要的。 因此学好 C 标准库能极大的提高编程效率。 3.2 什么是STL STL 即标准模板库Standard Template Library是 C 标准库的一部分 里面包含了⼀些模板化的通过用的数据结构和算法 。由于其模板化的特点它能够兼容自定义的数据类型避免大量的造轮子工作。 NOI 和 ICPC 赛事都支持 STL 库的使用当然 蓝桥杯也是支持的 。因此⼀定要学习 STL 的使用 能够极大的提高编写代码的效率。 3.3 怎么学习STL 模范使用 STL 的实现涉及比较⾼深的 C 知识 比如类、模板、容器适配器等 。如果想 搞清楚背后的原理就必须要学会这些知识。但是这些知识在竞赛中是用不到的如果深究会浪费 大量无用的时间。因此目前先把重点放在如何使用上。
