PPT 转换后部分内容有误，请查看下述单独页讲解截图。

演讲文稿

美国大选终于要告一段落，“按照美国选举人制度，候选人在各州赢得的选举人票累计超过538票的一半（270张），就当选总统。”如果让你编写统计票的算法，你会如何编写？

今天，就借以「摩尔投票」算法给大家讲解一下算法的一些基础概述，以及我们通过算法能达到哪些目的，带来哪些“收益”。

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

对于算法的了解我们首先要从其定义、要素、特征、指标、描述等几方面来讲解，接下来我们一一展开。

通常我们也可以理解为：“能够对一定规范的输入，在有限时间内获得所要求的输出。”

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

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

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

如何评定算法的好坏？

• 正确性：合法的输入数据得出满足要求的结果；
• 可读性：代码易于理解，晦涩难懂的算法易于隐藏较多错误而难以调试；
• 稳健性：充分考虑异常情况，并且处理出错的方法不能中断算法的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理；

高效率与低存储量，就是指的通常我们提到的“时间复杂度”和“空间复杂度”。

评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而，有的时候时间和空间却又是「鱼和熊掌」，不可兼得的，那么我们就需要从中去取一个平衡点。

对于开发者来说，在动手编写代码前，使用上面手段先将核算算法描述出来是一种值得推荐的做法。

对于算法的基础概念有了一定认知和掌握，那我们如何求解（创建算法）呢？

第一步“问题分析”，主要任务是对问题进行认真分析后，确认问题的逻辑结构和问题的基本功能，并在数学、物理等与问题领域相关知识的基础上建立数学模型。

第二步“算法设计”，是对处理功能的求解，即找出解决问题的处理步骤。

第三步“算法分析”，是对数学模型的建立、数据结构的选择及算法设计工作的评价、总结。

到此，一个算法的整个“生命”过程我们讲解完了。回到开始，如何找出“美国总统”获胜者？

采用上述的步骤我们先进行问题分析，得知，这是一个求“数组中出现次数超过一半的数字/名字”的问题。然后，设计算法。

遍历数组中所有“选票”，统计相同选票的总数，然后和数组长度的一半对比。

衡量算法，时间&空间复杂度：O(N)

示例中，我们简化了场景（一定有人获得大选胜利），那么我们对数组进行排序，在其中间位置必然为获胜者。

核心理念为票数正负抵消。

此方法时间和空间复杂度分别为 O(N) 和 O(1) 。

效率上显著提高。

如果多个人参与选举（非两人），且不一定有超过一半的人。那我们需要加入“计数阶段”。即，判断最终获胜人是否大于数组长度的一半。

总结：“用计算机求解问题”是算法的初衷，算法设计的优劣决定软件系统的性能。理论及实践结合，在现实的问题分析中，培养抽象思维和缜密概括的能力，是想要传达给大家的。