搜索品牌价值的网站,建设公司网站需要准备什么科目,建设搜索引擎网站,建设部网站继续教育一#xff1a;数据结构概论
数据结构分为初阶数据结构#xff08;主要由C语言实现#xff09;和高阶数据结构#xff08;由C实现#xff09;
初阶数据结构当中#xff0c;我们会学到顺序表、链表、栈和队列、二叉树、常见排序算法等内容。
高阶数据结构当中#xff0…一数据结构概论
数据结构分为初阶数据结构主要由C语言实现和高阶数据结构由C实现
初阶数据结构当中我们会学到顺序表、链表、栈和队列、二叉树、常见排序算法等内容。
高阶数据结构当中我们会学到图、哈希表、红黑数等内容。
二数据结构前言
1.数据结构
数据结构是计算机存储与组织数据的方式包括增加数据、删除数据、查找数据、改写数据等指相互之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有的用途都有用所以我们要学习各种各样的数据结构如线性表、树、图、哈希……
数组 int arr[4]{0,1,2,3};就是一个简单的数据结构。
可以插入删除查找修改其中的元素。
但是数组元素只能时同类型的数组这一单一的数据结构不是对所有的用途都有用比如不同类型的数据这时候我们就可以用另外一种数据结构————结构体。
2.算法
算法就是定义良好的计算过程它取一个或一组的值为输入并产生一个或一组值作为输出。简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果。
算法是有好坏之分效率高低之分的可以通过复杂度这一概念来判断算法的好坏。
算法和数据结构是紧密联系的二者不可分割。
如何学好算法与数据结构
1.死磕代码 2.画图画图画图思考
三算法效率
如何衡量一个算法的好坏呢
案例请看下面这道算法题https://leetcode.cn/problems/rotate-array/description/
思路循环K次每次将数组所有元素向后移一位。 代码点击执行可以通过然而点击提交却无法通过那该如何衡量其好与坏呢
1.复杂度的概念
算法在编写成可执行程序后运行时需要耗费时间资源和空间资源。
衡量一个算法的好与坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。
时间快慢————5ms VS 5s
空间占用内存大小————1G VS 1kB
时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间 在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的 迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。 2.复杂度的重要性
复杂度在校招中的考察已经很常见。
3.时间复杂度
定义在计算机科学中算法的时间复杂度是一个函数式T(N)它定量描述了该算法的运行时间。时间复杂度衡量程序的时间效率我们其实可以在程序中计算程序的运行时间。
用到C语言中的一个库函数clock#include time.h.
返回的时间单位是毫秒。 既然我们可以在程序中计算一个算法的运行时间那为什么还要引入时间复杂度这一概念呢
其实使用clock来计算算法的运行时间有一些弊端
1.这种计算算法运行时间的方法只能在编写完程序后再去计算。
2.当代电脑CPU处理数据的速度一秒可以执行上亿次对于循环次数较少的程序几种不同的算法打印出的结构可能都是0就没有办法比较算法的好坏了。
3.程序运行时间和编译环境和运行机器的配置都有关系比如同一个算法程序用一个老编译器和新编译器编译在同一台机器侠运行时间就不同。同一个程序用低配置的设备和高配置的设备运行时间也不同。
那我们有没有办法在想出有一种算法后就知道该算法的时间复杂度进而判断这个算法的好坏呢 这时候就要用到时间复杂度来进行判断。
算法的时间复杂度是一个函数式T(N)这个函数计算了程序的执行次数。通过C语言的学习我们知道算法编译后会形成二进制指令程序运行CPU就去执行这些指令。那么我们通过程序代码或者理论思想计算出程序的执⾏次数的函数式T(N)假设每 句指令执⾏时间基本⼀样(实际中有差别但是微乎其微)那么执⾏次数和运⾏时间就是等⽐正相关 这样也脱离了具体的编译运⾏环境。执⾏次数就可以代表程序时间效率的优劣。⽐如解决⼀个问题的 算法a程序T(N) N算法b程序T(N) N^2那么算法a的效率⼀定优于算法b。 接下来我们通过几个程序的案例来进一步加深对于一个算法时间复杂度的理解。
案例一 首先这个算法创建了变量count又进行了N次循环这N次循环中每次循环又嵌套了N次循环循环过后又进行了2*N次循环然后创建变量M在进行M次循环。M是一个确定的数
据此我们可以得出本程序的基本操作次数执行次数T(N)1N^22*N110
通过对N的取值分析当N越来越大时对结果影响最大的一项是N^2。
实际上我们计算复杂度时也只是粗略的计算算法大概的执行次数精确计算是很麻烦的不同的一个语句编译出的二进制指令是不同的CPU处理数据时一秒可以处理上亿条指令是可以允许一些计算误差的。
所以我们计算算法的时间复杂度时只需要计算程序的大概执行次数就可以了复杂度的表示通常使用大O的渐进表示法
大O的渐进表示法
推导大O规则
1.时间复杂度函数时TN中只保留最高阶项去掉那些低阶项因为当N不断增大时低阶项对结果的影响越来越小当N无穷大时就可以忽略不计了。
2.如果最高阶项存在且不是1则去除这个项目的常数系数因为当N不断增大时这个系数对结果的影响越来越小当N无穷大时就可以忽略不计了。
3.TN中如果没有N相关的项目只有常数项用常数项1取代所有加法常熟。
通过以上分析案例一的时间复杂度为O(N^2). 案例二 分析本算法进行了2*N次循环又进行了M次循环还进行了两次变量创建一次打印。
T(N)12*N1M1
忽略掉可忽略项 T(N)2*NM (M10)
又因为M是已知的。
所以根据大O的渐进表示法可得本算法的时间复杂ON。注意不是O2*N 案例三 本算法根据大O的渐近表示法可得时间复杂度为O(MN).
需要分类讨论{1.MN时———O(M) 2.MN时——O(N 3.M和N差不多时—O(M或O(N)} 案例四 本算法的执行次数为T(N)100;
根据大O的渐近表示法可的本算法的时间复杂度为O(1). 案例五 本算法的目的是进行查找字符在字符串中出现的位置
该算法的执行次数不是一个固定的值而是需要根据实际的情况来确定如果要查找的字符出现在字符串的前端执行次数相对就少。反之如果要查找的字符串出现在字符串的后端执行的系数就会较多。
如果要查找的字符出现在字符串的第一个位置T(N)1.
如果要查找的字符出现在字符串的最后位置T(N)N.
如果要查找的字符出现在字符串的中间T(N)N/2.(N为字符串的长度)
因此本算法的时间复杂度分为
最好情况O(1)
中间情况O(N)
最坏情况O(N) 案例六 冒泡排序的时间复杂度
趟数n-1 每趟内部n-1-i次
也是分情况讨论
1.若数组有序则T(N)N;
2.如果数组有序且为降序则T(N)N*(N-1)/2;
3.数组介于有序和无序之间。
判断一个算法的好坏要看最差的那种情况因此本算法的时间复杂度取ON^2。 案例七 本算法的执行次数直接分析的话不太容易
我们给n取值查找其中的规律
n1时 T0T指循环执行次数
n2时 T1 n4时 T2
n5时 T3
由此我们可以推断出规律 假设循环执行X次n2^X因此执行次数Tlog2X2是底数X是真数 因此func5的时间复杂度取最差情况为 O (log 2 n ) 案例八
