计算机基础专升本笔记七 – 计算思维

三大科学思维

①理论思维、②实验思维、③计算思维

一、计算思维的概念和特征

（1）计算思维的概念：计算思维是运用计算机科学的基础概念进行问题求解，系统设计以及人类行为等涵盖计算机科学之广度的一系列思维活动。
（2）计算思维的本质：抽象和自动化。
自动化反映了计算思维的根本问题，即什么能被有效的自动执行。
（3）计算思维的特征：
①概念化不是程序化；
②是根本的（基本的）技能，不是刻板的技能；
③是人的思维方式，不是计算机的思维方式；
④数学和工程思维互补和融合；
⑤是思想不是人造物；
⑥计算思维面向所有人，所有领域，所有地方。

二、计算思维的基本计算方法

（1）程序：程序 = 算法 + 数据结构；
（2）算法：算法是解决某一特定问题的一组有穷规则的集合；算法指一组有穷的指令集，是解决方案的准确而完整的描述；算法不等于程序；
（3）常用的算法：排序、穷举（枚举）、递归、迭代、分治、深度有点搜索（DFS）、广度优先搜索（BFS）、并行计算、动态规划（DP）；
（4）算法的五大特征：有穷性、确定性、可行性、输入/输出性；
（5）数据结构：数据结构是计算机存储、组织数据的方式，是相互之间存在一种或多种特定关系的数据元素的集合；
（6）常用的数据结构：数组，栈，链表，队列，树，图，堆，散列表等；
线性结构：线性表、栈、队列、串、数组；
非线性结构：广义表、树、图。

三、算法概论

（1）算法的概念：算法就是对计算思维解决问题的方法的描述是计算机求解的核心和关键。
（2）算法的基本特征：
①有穷性：算法必须能执行有线各步骤之后停止；
②确定性：算法的每一个步骤都必须有明确的定义不应该在理解时产生二义性；
③可行性：每个算法都可以有效地执行并能得到确定的结果；
④输入项：有0个或多个输入；
⑤ 输出项：有1个或多个输出。
（3）算法的控制结构（程序的基本结构）：
①顺序结构、②选择结构、③循环结构
（4）算法的描述方法：自然语言，流程图，伪代码，N-S图和PAD图等；
（5）算法复杂度：复杂度分为时间复杂度和空间复杂度；
①时间复杂度是执行算法所需要的计算工作量，即算法所执行的基本步数和指令的条数。
②空间复杂度是执行该算法所需要的内存空间。