算法--基础

版权声明:本文为博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://ligang.blog.csdn.net/article/details/83115975

学习算法设计的重点就是把人类找到的求解问题的方法、步骤以过程化、形式化、机械化的形式表示出来,以便让计算机执行。

算法概述

定义

算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。

要素

算法由操作、控制结构、数据结构3要素组成。

  • 操作 类型 说明 算术运算 加、减、乘、除 关系比较 大于、小于、等于、不等于 逻辑运算 与、或、非 数据传输 输入、输出、赋值
  • 控制结构 类型 说明 顺序结构 各操作是依次执行的 选择结构 由条件是否成立来决定选择执行 循环结构 操作重复执行,直到满足某个条件时才结束
  • 数据结构:算法操作的对象是数据,数据间的逻辑关系、数据的存储方式及处理方式就是数据结构。

基本特征

算法具有五个重要特征:有穷性、确切性、输入项、输出项、可行性。

  • 有穷性:必须能在执行有限个步骤之后终止;
  • 确切性:每一步骤必须有确切的定义;
  • 输入项:有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定出了初始条件;
  • 输出项:有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;
  • 可行性:任何计算步骤都是可以被分解为基本的可执行的操作步,即每个计算步都可以在有限时间内完成。

算法的质量指标

  • 正确性:合法的输入数据得出满足要求的结果;
  • 可读性:代码易于理解,晦涩难懂的算法易于隐藏较多错误而难以调试;
  • 稳健性:充分考虑异常情况,并且处理出错的方法不能中断算法的执行,而应是返回一个表示错误或错误性质的值,以便在更高的抽象层次上进行处理;
  • 高效率与低存储量:不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度时间复杂度来衡量。
    • 空间复杂度:算法在运行过程中临时占用存储空间大小的量度;
    • 时间复杂度(Asymptotic Time Complexity):算法的运行时间。 算法运行时间=∑原操作的执行次数∗原操作的执行时间 算法运行时间 = ∑原操作的执行次数 * 原操作的执行时间 算法运行时间=∑原操作的执行次数∗原操作的执行时间 对于复杂的算法计算运行时间,工作量很大。所以经常采用:最深层次循环体内的语句中的原操作。 分类:O(1)常数级、O(logn)对数级、O(n)线性级、O(nc)多项式级、O(cn)指数级、O(n!)阶乘级。

深入思考:P问题、NP问题及NPC问题:

  • P问题:所有可以由一个确定型图灵机在多项式表达的时间内解决的问题;
  • NP问题:所有可以在多项式时间内验证它的解是否正确的决定问题组成,或者等效的说,那些可以在非确定型图灵机上在多项式时间内找出解的问题的集合;
  • NPC问题:NP完全问题,是NP的一个子集,且其中每一个问题均能由NP中的任何问题在多项式时间内转化而成。如,背包问题、华容道游戏(由于搜索)等

补充: 确定型图灵机:同一个输入,按照惟一确定的方式进行运行。

算法描述

算法的方式主要有:自然语言、流程图、盒图、PAD图、伪代码和计算机程序设计语言。

  • 自然语言:日常所用语言,描述语句较长且容易产生歧义性;
  • 流程图:不易表述数据结构,层次感不强;
  • 盒图:不易扩充和修改,对于大型复杂算法较难描述;
  • PAD图:图形符号书写、编辑、录入不方便;

求解步骤

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券