计算机基础-算法

SunnyDusk Lv3

计算与计算思维

  1. 三大思维:实验思维、理论思维、计算思维
    (1). 实验思维:实验->观察->发现、推理与总结;观察与归纳
    (2). 理论思维:假设/预设->定义/性质/定理->证明;推理与演绎
    (3). 计算思维:设计,构造与计算;设计与构造
  2. 计算思维的概念
    运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解 等涵盖计算机科学之广度的一系列思维活动;
  3. 计算思维的本质:抽象、自动化
  4. 计算思维的特点/特征
    (1). 概念化,不是程序化;
    (2). 根本的,不是刻板的技能(内化);
    (3). 是人的,不是计算机的思维方式;
    (4). 数学和工程思维的互补与融合;
    (5). 是思想,不是人造物;
    (6). 是面向所有人,所有地方;
  5. 计算思维的四个步骤
    分解->模式识别->抽象化->算法
  6. 计算思维的应用领域
    计算机生物学、脑科学、计算化学、数学、计算经济学、工程(电子,海洋……)

算法

  1. 算法的概念
    按照一定规则解决一类问题的明确和有限的步骤
  2. 算法的特性
    (1). 有穷性:算法必须能在执行有限个步骤之后终止;
    (2). 确定性:算法中每一条指令必须有确切的含义,不会出现二义性;
    (3). 可行性:算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现;
    (4). 输入:一个算法有零个或多个输入,这些输入取自某个特定的对象的集合;
    (5). 输出:一个算法有一个或多个输出,这些输出同输入有着某种特定关系;
    注:算法可以无输入,必须有输出
  3. 算法的评价
    解决同一个问题可以有多种算法,算法有效率高低之分,评价标准有两个:时间标准—>时间复杂度;空间标准—空间复杂度
  4. 算法的时间复杂度
    度量一个程序的执行时间有两种方法:事后统计法、事前分析估算法
    语句频度:一个算法中语句执行的次数
    渐进时间复杂度:算法的时间复杂度,记作:T(n)=O(f(n)),其中f(n)是语句频度函数,简称时间复杂度;
    时间复杂度排序:O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<<O(2n)<O(n!)<O(nn)O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<……<O(2^n)<O(n!)<O(n^n)
    时间复杂度越大,算法的效率越低
  5. 算法的设计要求
    (1). 正确性:算法(应当满足具体问题的需求)的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案;
    (2). 可读性:算法应当方便人们阅读和交流;
    (3). 健壮性:当输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果;
    (4). 时间效率高和存储量低:算法执行时间短,运行所需存储空间低;

数据结构

  1. 数据结构的概念
    研究非数值计算的程序设计中计算机的操作对象以及他们之间的关系操作等相关问题的学科;
  2. 数据结构包含:逻辑结构、存储结构、数据操作
    (1). 逻辑结构:数据元素之间的逻辑关系;
    (2). 存储结构:数据结构在计算机中的表示;
    (3). 数据操作:检索、删除、插入,对数据元素的操作;
  3. 逻辑结构包含的基本种类:集合结构、线性结构、树形结构、图形结构
    (1). 集合结构:集合结构中的数据元素除了同属于一个集合外,它们之间没有其他关系;
    (2). 线性结构:线性结构中的数据元素之间是一对一的关系;
    (3). 树形结构:树形结构中的数据元素之间存在一种一对多的层次关系;
    (4). 图形结构(网状):图形结构的数据元素是多对多的关系;
  4. 存储结构包含的基本种类:顺序存储结构、链式存储结构、索引存储结构、散列存储结构;

    (1). 顺序存储结构:把数据元素存放在地址连续(相邻)的存储单元里,其数据间的逻辑关系和物理关系是一致的;可以实现随机存取
    (2). 链式存储结构:把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的;可以顺序存取,也可以随机存取
    (3). 索引存储结构:除了存储数据元素信息外,还建立附加的索引表,通过索引表找到存储数据元素的地址;
    (4). 散列存储结构:根据关键字直接计算出该关键字对应的存储地址,将值为关键字的记录存放在计算出的存储地址上;
  5. 总结

    线性结构:
    队列:先进先出;
    栈:先进后出;

程序

  1. 程序的概念
    程序定义:是由有序指令组成的序列,用于完成特定功能。
    软件定义:使计算机运行所需的程序、数据及有关文档的总和;
    软件包括程序,程序不一定是软件
    算法是程序的核心
  2. 程序设计的步骤

    (1). 分析问题:分析问题的特点,确定解决问题的方法;
    (2). 设计算法:设计解决问题的算法,确定解决问题的步骤;
    (3). 编写程序:用某种程序设计语言编写程序;
    (4). 调试程序:调试程序,使程序能够正确运行;
    (5). 测试程序:测试程序,使程序能够正确运行;
    (6). 维护程序:维护程序,使程序能够正确运行;
  3. 结构化程序设计的基本控制结构
    (1). 顺序结构:程序按先后次序,依次执行,不发生跳转;按照语句的先后顺序执行,说啥算法中最简单的一种结构
    (2). 选择结构(分支结构):根据条件选择是否选择执行路径;根据条件的不同,程序执行不同的语句
    (3). 循环结构:根据条件重复执行的程序段;循环三要素:循环变量、循环体、循环终止条件;根据判断条件,循环结构可以细分为:当型和直到型;根据约束条件的不同多次重复执行某条或多条的结构
  4. 面向过程的结构化程序设计原则自顶向下、逐步求精、模块化
  5. 算法的表示方法
    (1). 自然语言描述:人类日常生活中使用的语言,描述算法通俗易懂,但缺乏直观性和简洁性,用自然语言描述算法的思想;
    (2). 流程图:算法的图形化表示方法,与自然语言相比,它的描述形象直观更易理解,用符号表示算法;

    (3). 伪代码:介于自然语言和计算机程序之间的算法描述,没有严格的语法限制,用伪代码描述算法的思想;
    (4). N-S:简化的流程图,去掉了流程图中的流程线,全部写在一个矩形框内,用程序设计语言描述算法的思想;
  6. 面向对象方法学
    最常用的程序设计方法包括两类:面向过程程序设计方法、面向对象程序设计方法
    (1). 面向过程程序设计方法:程序是一系列的步骤,每一步骤都是对数据的处理;
    (2). 面向对象程序设计方法:程序是一系列的对象,每个对象都有自己的数据和操作(模拟人类习惯的思维方式);
  7. 面向对象方法学的优点
    (1). 使程序设计更加接近人类的思维方式;
    (2). 稳定性好;
    (3). 可重用性好;
    (4). 较易开发大型软件产品;
    (5). 可维护性好;
  8. 面向对象方法学基本概念
    (1). 对象:具有唯一标识状态行为的实体;由描述对象属性的数据以及对这些数据施加的所有操作封装在一起的统一体;
    对象的特点:
    ①. 以数据为中心;
    ②. 对象是主动的;
    ③. 实现了数据封装;
    ④. 本质上具有并行性;
    ⑤. 模块独立性好;
    (2). 类:具有相同属性和行为(操作)的对象的集合;
    (3). 封装:将数据和对数据的操作封装在一起,形成一个独立的整体(信息隐蔽);
    (4). 继承:子类继承父类(基类)的属性和行为;
    (5). 多态:同一操作作用于不同的对象,可以有不同的解释,产生不同的执行结果;
  9. 要点
    客观世界是由对象构成的,任何事物都是对象,复杂对象可以由简单对象构成;
    所有对象都划分称为,类是对象的抽象,类是对象的模板;
    按照子类父类的关系,类可以划分为子类父类
    对象彼此之间通过消息进行通信;
  • 标题: 计算机基础-算法
  • 作者: SunnyDusk
  • 创建于 : 2023-12-09 05:56:16
  • 更新于 : 2024-09-10 02:06:49
  • 链接: https://www.030706.xyz,https//www.sunnydusk.cn/2023/12/09/计算机基础算法/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
计算机基础-算法