数据结构与算法相关

什么是算法( 算法

算法(algorithm),在数学(算学)和电脑科学之中,为任何良定义的具体计算步骤的一个序列,常用于计算、数据处理和自动推理。精确而言,算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。
以下是高德纳在他的著作《计算机程序设计艺术》里对算法的特征归纳:

  • 输入:一个算法必须有零个或以上输入量。
  • 输出:一个算法应有一个或以上输出量,输出量是算法计算的结果。
  • 明确性:算法的描述必须无歧义,以保证算法的实际执行结果是精确地匹配要求或期望,通常要求实际运行结果是确定的。
  • 有限性:依据图灵的定义,一个算法是能够被任何图灵完备系统模拟的一串运算,而图灵机只有有限个状态、有限个输入符号和有限个转移函数(指令)。而一些定义更规定算法必须在有限个步骤内完成任务。
  • 有效性:又称可行性。能够实现,算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。
    常见算法分类:
  • 分治法:把一个问题分区成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。
  • 动态规划法:当问题的整体最优解就是由局部最优解组成的时候,经常采用的一种方法。
  • 贪婪算法:常见的近似求解思路。当问题的整体最优解不是(或无法证明是)由局部最优解组成,且对解的最优性没有要求的时候,可以采用的一种方法。
  • 线性规划法
  • 简并法:把一个问题通过逻辑或数学推理,简化成与之等价或者近似的、相对简单的模型,进而求解的方法。

什么是数据结构(数据结构

在计算机科学中,数据结构(英语:data structure)是计算机中存储、组织数据的方式。

  1. 常见的数据结构
    1. 数组(Array)
    2. 堆栈(Stack)
      • 先进后出
      • 可以用数组实现
      • 举例:盗梦空间
    3. 队列(Queue)
      • 先进先出
      • 可以用数组实现
      • 举例:排队
    4. 链表(Linked List)
      • 数组无法直接删除中间的一项,链表可以
      • 用哈希(JS里面用对象表示哈希)实现链表
      • head、node 概念
    5. 树(Tree)
      • 举例:层级结构、DOM
      • 概念:层数、深度、节点个数
      • 二叉树
      • 满二叉树
      • 完全二叉树
      • 完全二叉树和满二叉树可以用数组实现
      • 其他树可以用哈希(对象)实现
      • 操作:增删改查
      • 堆排序用到了 tree
      • 其他:B树、红黑树、AVL树
    6. 图(Graph)
    7. 堆积(Heap)
    8. 哈希表(Hash)
      • 计数排序中的桶(复杂度 O(n+max),比快排还快
      • 桶排序 与计数排序的区别
      • 基数排序 与计数排序的区别
  2. 数据结构和算法是互相依存、不可分开的
    1. 我们要解决一个跟数据相关的问题。
    2. 分析这个问题,想出对应的数据结构。
    3. 分析数据结构,想出算法。

堆排序可视化
堆排序JS代码完整讲解