对数据结构的初步认识

这篇具有很好参考价值的文章主要介绍了对数据结构的初步认识。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

对数据结构的初步认识

前言:

牛牛开始更新数据结构的知识了.本专栏后续会分享用c语言实现顺序表,链表,二叉树,队列,排序算法等相关知识,欢迎友友们互相学习,可以私信互相讨论哦!

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻推荐专栏: 🍔🍟🌯 c语言初阶
🔑个人信条: 🌵知行合一
🍉本篇简介:>:讲解数据结构的入门知识,时间复杂度与空间复杂度,以及一些对学习数据结构的建议.
金句分享:
✨最快的脚步不是冲刺,而是坚持!✨

1、数据结构是什么?

数据结构+算法=程序.

数据结构(Data Structure):是计算机存储、组织数据方式,指相互之间存在一种或多种特定关系的数据元素的集合。
例如后面会提到的顺序表,链表这些线性数据结构,还有后面的二叉树树形数据结构等.

对数据结构的初步认识对数据结构的初步认识对数据结构的初步认识对数据结构的初步认识

算法(Algorithm):就是定义良好的计算过程,他取一个或一组的值为输入,并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果.
例如:排序算法.

数据结构与算法对于一个程序员是很重要的,不论对你思考问题的方式还是对你编程的思维都会有很大的好处。同时在找工作时算法也是一个重要考点之一.

2、数据结构应该怎么学呢?

1.多多练习代码.
对数据结构的初步认识

数据结构的学习并不简单,需要多锻炼代码能力,最怕偷懒,很多时候头脑虽然理解了,但是动起手来写代码会忽略很多细节,导致程序出错,不能光有思路,而代码能力却实现不了就很尴尬了.

2.多画图(这个强烈推荐)
对数据结构的初步认识

除了代码能力需要锻炼以外,很重要的一点是要有思路,通过画图辅助,可以很好地帮助我们找到思路和理解数据结构中的很多思想,切忌上来就开始码代码,这样对于简单的问题可能可以解决,但是对于稍微复杂的问题可能会让你头痛(大佬除外😂😂),很容易被绕进去,陷入痛苦的调试找bug环节.
画图会让提供给我们清晰的思路,同时,即使出现了bug,也可以很快的找到,清晰可见.写代码只是用于实现思路,思路清晰,代码写起来并不困难.

3.刷题
刷题会锻炼我们的思考能力,解题是一种很灵活的事情.一方面可以巩固我们学的基础知识,另一方面可以拓展思维.
最后,坚持学习才是最重要的.
对数据结构的初步认识

算法效率如何衡量?

对于一个问题,可以有很多解法,那怎样衡量一个算法的好坏呢?
比谁的代码更简洁吗?
算法的效率主要考虑两点:1.时间复杂度. 2.空间复杂度

一个算法在编译生成可执行文件后,运行时会耗费时间资源和空间(内存)资源
从时间和空间两个维度来衡量一个算法的好坏是比较合理的,这就是时间复杂度空间复杂度

时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

一、 时间复杂度

时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一个算法执行所耗费的时间.

但是从理论上说,这个只有将代码进行测试,并统计时间才能知道.并不能通过计算得到.
但对于每一个算法,我们都去跑一下,这未免显得有些麻烦,我们可以通过算法中的代码估计运行大概的时间,看看属于哪一个量级来衡量它的效率.

算法中的基本操作的执行次数,为算法的时间复杂度。
即:找到某条基本语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度

理论不是很理解的话,我们来点实际的,找几段代码算算吧!

🌰小试牛刀
你能算出在test1中++count语句最终被执行了多少次吗?

void test1(int N)
{
	int count = 0;
	//1
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			++count;
		}
	}
	//2
	for (int k = 1; k < N; k*=2)
	{
		++count;
	}
	//3
	for (int k = 0; k < 2 * N; k++)
	{
		++count;
	}
	//4
	int a = 100;
	while (a--)
	{
		++count;
	}
	printf("%d\n", count);
}

答案:
1: N * N
2: log2 N
3. 2*N
4. 100

则我们可以抽象出这样的数学公式:

   test(N)=N2 +log2 N+2N+100

对数据结构的初步认识

大O的渐进表示法

计算机的运行速度是很快的,对于时间复杂度的计算,没有必要追求那么精确,对于那些对结果影响不大的项,我们可以忽略不计.如果我们只保留N2这一起决定因素的项.
对数据结构的初步认识

大O阶方法计算方法:

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

使用大O的渐进表示法以后,test1的时间复杂度为:

(O)N ^ 2

即使是100N系数也应当去掉,因为当数据足够大的时候100的影响并不大.
只要是常数,都应当是1.
也许你会认为100很大或者100000很大.但是,要看和谁比,如果是和10亿比呢?一万亿比呢?
那我们打个比方:

你觉得你们学校大吗?还行.
你所在的城市大吗?算大吧!
你觉得我们的祖国大吗?地大物博,确实大.

但是,与太阳系相比呢?与银河系相比呢?这就显得很渺小了,沧海之一粟罢了.
所以当数据量足够大的时候,常数项和那些影响不大的忽略不计.

对数据结构的初步认识

时间复杂度的练习:

1.1 常见的时间复杂度:

例1:

// 计算Test2的时间复杂度?
void Test2(int N)
{
	 int count = 0;
	 for (int i = 0; i < 2 * N ; i++)
	 {
	 	++count;
	 }
	 int M = 10;
	 while (M--)
	 {
		 ++count;
	 }
	 printf("%d\n", count);
	}

例2:

// 计算Test3的时间复杂度?
void Test3(int N, int M)
{
	 int count = 0;
	 for (int i = 0; k < M; i++)
	 {
	 	++count;
	 }
	 for (int i = 0; i < N ; i++)
	 {
		 ++count;
	 }
	 printf("%d\n", count);
}

例3:

// 计算Test4的时间复杂度?
void Test4(int N)
{
	 int count = 0;
	 for (int i = 0; i < 10000; i++)
	 {
		 ++count;
	 }
	 printf("%d\n", count);
}

答案:
这三个例子的时间复杂度还是很好计算的.
例1:

2N+10用大O表示法表示时间复杂度为O(N).

例2:

基本操作执行了M+N次,有两个未知数M和N,时间复杂度为 O(N+M)
如果m和n相等则可以表示为O(N),如果一方远大于另一方,则可以用大的一方表示,记住是远大于,即不在一个量级.

例3:

基本操作语句被执行了常数次.这用大O表示法表示时间复杂度为O(1).

那试着分析TargetNum函数的时间复杂度.
TargetNum函数是用于在一个数组中查找目标值的函数,找到了就返回目标值的地址,没找到就返回NULL.

int* TargetNum(int* arr,int n, int num)
{
	for (int i = 0; i < n; i++)
	{
		if (arr[i] == num)//找到目标数字则返回数字的地址
		{
			return arr + i;
		}
	}
	return NULL;
}
int main()
{
	int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int num = 0;
	scanf("%d", &num);
	int*ret =TargetNum(arr, sz, num);
	if (ret == NULL)
	{
		printf("该目标值不存在");
	}
	printf("%d ", *(ret));
	if (ret + 1 <= &arr[sz - 1])
	{
		printf("%d ", *(ret + 1));
	}
}

此时就让人有些疑惑了,这个函数的时间复杂度似乎不是固定的.在1~n的范围之间的那如何确定它的时间复杂度呢?
对数据结构的初步认识

分析一下:
最好情况时(第一个数就是目标值): O(1).
平均情况时:O(n/2).
最坏情况时:O(n).

那我们选择哪种情况比较合理呢?
那我们讲一个小故事吧.

假如你是一名高中生,你刚经历期末考试,晚上,老师只公布了部分答案.
你可以确保自己可以拿到60分,有剩余的40分中,你按照以往的每次考试的经验来看,不出意外20分是可以拿到的.
此时回到家中,老爸问你能考多少分?考多少分老爸就奖励你多少钱,嘿嘿.🍭🍭🍭
你会说80(平均情况)分吗?还是会选择100分(最好情况)呢?
万一食言了呢?
咱一般都会选择最坏的情况,那样即使出现了意外,我们也没有说错,而不出意外时,无论是平均还是最好情况,我们都会比较高兴的.

这里牛牛也想告诉大家,结局未定之前,不要过分高看自己,降低期望,当然也不要自卑,继续努力,继续前行,保持对生活的热爱,生活也会拥抱你的!🍭🍭🍭

回到正题,此时我们会选择最坏的情况作为时间复杂度,即TargetNum函数的时间复杂度是O(n).

1.2 冒泡排序的时间复杂度

大家还记得c语言时学的冒泡排序吗?

// 计算BubbleSort的时间复杂度?
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(0)或者O(1).
首先呢,没有O(0)这一说法,这几乎不可能,其次这里最好的情况也不是O(1),为什么呢?
如果数组有序,那不就不需要排序吗?那不就是O(1)吗?

其实,即使数组有序,我们也需要循环遍历一遍这个数组,才能知道有序,计算机不是人哦,他不能看一眼就知道有序,而且就算是人,当数据量比较大的时候人一眼也看不出来是否有序吧!
总结:
最好情况:O(N)
最坏情况:O(N2)

1.3 "二分查找"的时间复杂度

int BinarySearch(int* a, int n, int x)
{
	 assert(a);
	 int begin = 0;
	 int end = n-1;
	 while (begin <= end)
	 {
	 	int mid = (begin+end)/2;//找到中间值
	 	if (a[mid] < x)//如果该值比中间值大,则直接从中间值的后半部分里面找
		{
		 	begin = mid+1;
		}
		else if (a[mid] > x)//如果该值比中间值小,则直接从中间值的前半部分里面找
		 {
		 	end = mid-1;
		 }
	 	else//找到了
	 		return mid;
	 }
	 //没找到返回-1,这里设置为-1也许有些不合理,可以使用逻辑值.
	 return -1;
}

判断一次(与中间值比较),就可以去掉一半的值.即该算法一次N的值就会等于N/2.
不难得出该算法的时间复杂度是O(logn2).

补充知识:logn2经常省略写成log2甚至lg2

"二分查找"看起来平平无奇,但其实是个隐藏的大佬啊!
大家知道这些量级的差距有多大吗?log2是很可怕的量级,速度极快.
看图感受一下吧!

对数据结构的初步认识

友友们感受到二分查找的厉害了吧!

遗憾的是,二分查找的前提是数据得是有序的,否则他无法实现一次排除一半.而数据往往是无序的,并且有些特殊的数据还不允许排序,排序会破坏数据的.
这也就让二分查找无计可施了,纸老虎罢了.😂😂😂

1.4 递归的时间复杂度:

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

递归的时间复杂度计算主要是根据其递归的层数来决定.
该算法每次递归N就-1,则递归的次数为N.
故算法的时间复杂度为:O(N).

// 计算斐波那契递归Fib的时间复杂度?
int Fib(int N)
{
	 if(N < 3)
	 return 1;
	 
	 return Fib(N-1) + Fib(N-2);
}

此算法,每次经过递归都需要再递归2 * N次.
对数据结构的初步认识
则此算法的时间复杂度为O(2n).

常见量级的比较图

大O的渐进表示法:
对数据结构的初步认识

二、空间复杂度

空间复杂度并不是重点,现如今,一般情况下我们的时间的价值比空间的价值要高的多.
定义:

空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少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;
	 }
}

为了实现冒泡排序我们定义了int exchange = 0;以及Swap(&a[i-1], &a[i]);函数中的int tmp.
这项常数个临时变量,故空间复杂度为O(1).

例2:

int Fac(int N)
{
	 if(0 == N)//递归的结束条件
	 {
	 	return 1;
	 }
	 
	 return Fac(N-1)*N;
}

同样递归的空间复杂度由开辟的栈帧个数(每次递归开辟一次栈帧)决定,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N).

好了,数据结构的初步认识就到这里啦!后续牛牛会继续更新数据结构的相关知识.
如果文章对大家有用的话记得一键三连哦!💗💗💗
如果文章中有部分错误之处,可以私信牛牛,互相讨论哦!!!

对数据结构的初步认识文章来源地址https://www.toymoban.com/news/detail-428594.html

到了这里,关于对数据结构的初步认识的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • MySql数据库的初步安装与数据表结构数据管理

    目录 一、数据库的相关了解 1)数据库的概念  数据(Data) 表 数据库系统 2)数据库系统发展史 第一代数据库 第二代数据库 第三代数据库 当今主流数据库介绍 2)数据库的分类  关系数据库 非关系型数据库 非关系型数据库的优点 二、mysql的yum安装与源码编译安装   1)源

    2024年02月08日
    浏览(388)
  • 【数据结构】树的认识

    一个人的未来不是预测出来的,而是创造出来的。                        -- 亚当·詹姆斯 目录 🍁前言: 🍀一.什么是树? 🍑二.树有什么用?  ❤️1. 数据库 🧡2. 文件系统 💛3. 编程语言 💚4. 网络 💜5. 人工智能 🍂三.树的基础知识 🌳四.树的存储结构 🍐1.双亲表示

    2024年02月06日
    浏览(45)
  • 【数据结构】 简单认识包装类与泛型

    在Java中,由于基本类型不是继承自Object,为了在 泛型代码 中可以支持基本类型,Java给每个基本类型都对应了一个包装类型。 除了 Integer 和 Character, 其余基本类型的包装类都是首字母大写。 装箱就是自动将基本数据类型转换为包装器类型;拆箱就是自动将包装器类型转换

    2024年02月12日
    浏览(47)
  • 深入学习 Redis - 常用数据类型,结构认识

    目录 一、Redis数据类型  Redis 数据类型结构简单认识 每个数据类型具体的编码方式 1.string  2.hash 3.list 4.set 5.zset 典中典:记数字!!! 6.查看 key 对应 value  的实际编码方式 如果本文有帮助到你,不妨给个三连吧~ Redis 中所有的 key 都是 string 类型,不同的是 value 的数据类型

    2024年02月16日
    浏览(53)
  • 【数据结构】认识链表和模拟实现单链表

    即使骑的小电驴,也要奋力前进 目录 1.链表 1.1 链表的概念  1.2 链表的逻辑结构图和物理结构图 1.2.1 链表的逻辑结构图  1.2.2 链表的物理结构图  1.3链表结构的分类 1.3.1 链表通过什么进行结构的分类  1.3.2 不同链表结构的逻辑图 2.模拟实现一个单向链表  2.1 MyLinkedList类的

    2024年02月14日
    浏览(57)
  • 【从零开始学习Redis | 第八篇】认识Redis底层数据结构(下)

    目录 前言:   ZipList: Ziplist的特性: QucikList: QuicList特征: SkipList: 跳表特征: RedisObijct:  小心得: 总结:           在现代软件开发中,数据存储和处理是至关重要的一环。为了高效地管理数据,并实现快速的读写操作,各种数据库技术应运而生。其中,Redis作为一种

    2024年04月12日
    浏览(51)
  • [JAVA数据结构] 认识 Iterable、Collection、List 的常见方法签名以及含义

            (一)Iterable                 1. 介绍                 2. 常见方法         (二)Collection                 1. 介绍                  2. 常见方法         (三) List                  1. 介绍                 2. 常见方法

    2024年02月02日
    浏览(43)
  • 数据结构进阶篇 之 【二叉树】详细概念讲解(带你认识何为二叉树及其性质)

    有朋自远方来,必先苦其心志,劳其筋骨,饿其体肤,空乏其身,鞭数十,驱之别院 1.1 二叉树中组分构成名词概念 1.2 二叉树的结构概念 1.3 特殊的二叉树 2.1 顺序存储 2.2 链式存储 前言: 在你的想象中如果有一个“二叉树”会是什么样子呢? 顾名思义,现实中的二叉树我们

    2024年04月13日
    浏览(44)
  • 数据结构之链表 - 超详细的教程,手把手教你认识并运用链表

    顺序表只适合静态的查找和更新,不适合插入和删除元素, 因为在ArrayList中插入和删除元素时,由于需要将后序元素往前后者往后移动,所以时间复杂度会相当高,能达到O(N)。 为了解决这一问题,java 引入了 LinkedList(链表)。 链表是一种 逻辑上连续,物理上不连续 的存储结

    2024年02月09日
    浏览(60)
  • 数据结构之栈和队列 - 超详细的教程,手把手教你认识并运用栈和队列

    栈:后进先出 队列:先进先出 栈:是一种特殊的 线性表 , 只允许在固定的一端插入或者删除元素 ,一个栈包含了栈顶和栈底。只能在栈顶插入或者删除元素。 栈的底层 是由 数组 实现的。 栈遵循先入后出原则,也就是先插入的元素得到后面才能删除,后面插入的元素比

    2024年02月07日
    浏览(78)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包