数据结构与算法
问题:
1、什么是数据结构?数据结构都有哪些类型?
2、算法的定义?如果评估一个算法的效率呢?
3、数据结构和算法之间有着什么样的关系呢?
Answers:
学习数据结构和算法的前提是首先要理解数据结构和算法的概念,只有理解了它们的概念才能找到好的学习方法,抓住学习的重点。
1、什么是数据结构?
数据结构就是指一组数据的组织、管理和存储方式。其使用目的是为了高效的访问和修改数据。
数据结构都有哪些类型?
1、线性结构,线性结构是最简单的数据结构,包括:数组、链表、栈、队列、散列表
2、树形结构,树形结构是相对复杂的数据机构,表示一种一对多的关联关系,包括:二叉树、二叉堆、Trie 树
3、图形结构,表示一种多对多的关联关系,包括:图
2、什么是算法呢?
算法就是操作数据的一组方法。包括:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法等;
那如果评估一个算法的效率呢?
评估算法的执行效率有三个参考点:
1、时间复杂度,对算法执行时间长短的度量,用O表示,记作T(n)=O(fn),常见的时间复杂度从低到高的顺序是 O(1) < O(logn) < O(n) < O(nlogn) < O(n^2)
如何推导时间复杂度呢?
1.1、如果运行时间是常量级,则用常数1表示
1.2、只保留时间函数中的最高阶项
1.3、如果最高阶项存在,则省去最高阶项前面的常数
2、空间复杂度,对算法在运行过程中临时占用存储空间大小的度量,用O表示,记作,S(n) = O(fn),常见的空间复杂度按照从低到高的顺序是 O(1) < O(n) < O(n^2),递归算法的空间复杂度和递归深度成正比
3、数据的稳定性,在排序过程如果相同数据的前后次序未发生变化,则排序是稳定的,否则排序不不稳定的。在使用排序算法或者选择排序算法时,更希望这个次序不会改变,更加稳定,所以排序算法的稳定性,是一个特别重要的参数衡量指标依据。
3、那数据结构和算法有什么关系呢?
数据结构和算法是相辅相成的。数据结构是为算法服务的,算法要作用在特定的数据结构之上。
举个例子:
图书管理员一般会将书籍分门别类进行“存储”。按照一定规律编号,就是书籍这种“数据”的存储结构。那我们如何来查找🈷️i一本书呢?有很多种办法,你可以一本一本的找,也可以根据书籍的类别是科学、历史、小说等来定位查找,这些查找方法都是算法,只是查找效率不同而已。