计算思维学习笔记

专升本计算机第十一章计算思维，内容有计算思维、问题求解、程序与算法、算法设计的基本方法、排序与查找、程序设计一般过程、程序设计方法等。

第十一章 计算思维

• 计算思维
  • 本质
    • 抽象，是前提和基础（思考的过程）
    • 自动化（一步步执行）
  • 目的
    • 问题求解，系统设计，人类思维理解
  • 特征
    • 1. 计算思维是人的，不是计算机的
    • 2. 是根本的，而不是刻板的技能
    • 3. 是概念化的，而不是程序化的
    • 4. 是思想，而不是人造物
• 问题求解
  • 过程
    • 抽象
      • 形式化（思考的过程）
      • 数学建模（计算）
    • 自动化
      • 设计算法
      • 编写程序
• 程序与算法
  • 程序
    • 数据结构
      • 栈：先进后出
      • 队列：先进先出
    • 算法（核心）
  • 算法
    • 两个要素
      • 操作
        • 算术运算
        • 关系运算
        • 逻辑运算：与或非
        • 数据传达：输入，输出，赋值
      • 控制结构
        • 顺序结构：最简单
        • 选择结构：有条件
        • 循环结构
          • 当型：先判条件再循环 （有可能一次也不执行）
          • 直到型：先循环再判条件 （至少执行一次）
  • 算法的特性
    • 有穷性
    • 确定性：无二义，精确定义
    • 可行性
    • 输入：0个或多个结果
    • 输出：1个或多个结果
  • 分类
    • 数值
    • 非数值
  • 表示
    • 自然语言
    • 数据流程图
    • 伪代码
    • 计算机语言
  • 算法的复杂度 （用O表示）
    • 从时间复杂度和空间复杂度考虑：时间复杂度越高，算法处理时间越长
    • 时间复杂度计算规则
      • 忽略常数项
      • 忽略低次幂
      • 忽略高次幂的常数系数
      • 如果全为常数，时间密度位O（1）
      • eg ：2n4n方 时间密度为O（n方）
    • 时间复杂度大小顺序
• 算法设计基本方法
  • 迭代法
    • 旧推新 eg:斐波那契数列
  • 穷举搜索法
    • 列所有可能
  • 递归法
    • 自己调用自己
  • 回溯法
    • 试探法 eg：八皇后问题
  • 贪婪法
    • 局部最优，不一定获得全局最优
  • 分治法
    • 分--治--分
• 排序与查找
  • 排序
    • 选择排序
      • 选最大/小，放开头，依次
    • 冒泡排序
      • 从小到大，大数下沉
  • 查找
    • 顺序查找
      • 最优查找次数：1次
      • 最劣 ：n次
      • 平均 ：（1+n）/2次
    • 二分法查找
      • 前提：先按关键字大小排序
• 程序设计一般过程
  • 分析问题
  • 选择数学模型
  • 计算设计
  • 程序的编写，编辑，编译和连接
  • 运行和测试
• 程序设计方法
  • 结构化程序设计
    • 特点
      • 基于顺序，选择，循环3种基本控制结构
      • 自顶向下，逐步细化
      • 单入口，单出口
    • 缺点
      • 无法适应大规模软件设计
      • 可重用性差
  • 面向对象程序设计
    • 优点
      • 可适应大规模软件设计
      • 可重用性好
      • 符合人的习惯思维
      • 易于软件维护和功能增减
• 面向对象程序设计方法及举例
  • 对象
    • 对象名
    • 属性：是静态特征
    • 方法：操作，是动态（行为）
  • 类
    • 相同属性操作集合
  • 消息
    • 实现对象与对象之间的通信
  • 事件