|
|
|
瑞士计算机科学家Niklaus Wirth在1976年写了一本书，名为《算法+数据结构=编程》。从此我们的大学专业课终究多了一门课程，数据结构与算法，这也成为现在面试过程中，无论是大厂还是一些其他企业，在考察面试者的时候的一个重点内容（好难啊）
数据：对客观事物的符号表示
数据元素：数据的基本单位
数据对象：性质相同的数据元素的集合
数据结构：相互之间存在一种或多种特定关系的数据元素的集合
时间复杂度：评估执行程序所需的时间。可以估算出程序对处理器的使用程度
空间复杂度：评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度
注意点：
1、大O符号（Big O notation）是用于描述函数渐进行为的数学符号。更确切地说，它是用另一个（通常更简单的）函数来描述一个函数数量级的渐近上界。在数学中，它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项；在计算机科学中，它在分析算法复杂性的方面非常有用。
2、what is O?:"O"是数学符号，它的严格定义是"若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤C?f(n)。"用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。
3、时间频度
一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
4、时间复杂度
在时间频度T(n)中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律，为此我们引入时间复杂度的概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，它称为算法的渐进时间复杂度，简称时间复杂度。
5、推导大O阶，我们可以按照如下的规则来进行推导，得到的结果就是大O表示法：
1.用常数1来取代运行时间中所有加法常数。 2.修改后的运行次数函数中，只保留最高阶项 3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。
在了解了这些基础内容之后，为了面对面试过程中的算法题，可能接下来的操作就是各种刷题，不过，知其然也要知其所以然，不然后期在准备的时候又要花费大量的时间，
主要描述抽象数据类型，给出算法的基本概念和复杂度分析与评价方法，并讨论几乎每章都要用到的递归和回溯技术。
递归和回溯
介绍基本数据结构，包括链表、栈、队列、树、优先队列、堆、并查集和图，对于每一种数据结构分别采用多个实例进行具体的演示。
链表
栈
树
优先队列和堆
并查集ADT
图算法
[indent,需要这些资料的，关注+转发后，私信“资料”即可查看获取方式
[/indent,第三部分(第10~15章)介绍数据处理的技术，包括排序、查找、选择、符号表、散列和字符串算法。
排序
查找
选择算法(中位数)
符号表
散列
字符串算法
第四部分(第16~21章)重点介绍一些常用的算法设计技术及应用，包括贪婪算法、分治算法、动态规划算法、复杂度类型，并讨论对于面试和考试的一些有用话题。
贪婪算法
动态规划算法
杂谈
[indent,书籍和思维导图已经准备好了，需要这些资料的，关注+转发后，私信“资料”即可查看获取方式
[/indent, |
|
发表于 2020-8-12 17:55:17
