对数据结构的初步认识

前言:

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

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

目录

• 前言:
• • 1、数据结构是什么?
  • 2、数据结构应该怎么学呢?
• 算法效率如何衡量?
• • 一、 时间复杂度
  • • 大O的渐进表示法
    • 时间复杂度的练习:
    • 1.1 常见的时间复杂度:
    • 1.2 冒泡排序的时间复杂度
    • 1.3 “二分查找”的时间复杂度
    • 1.4 递归的时间复杂度:
    • 常见量级的比较图
  • 二、空间复杂度

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: log₂ N
3. 2*N
4. 100

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

   test(N)=N² +log₂ N+2N+100