计算思维

有人说程序设计的本质是数学，而且还是一门应用数学，理由是过去程序设计的目标基本上就是为了数学的计算能力。随着信息与网络科技的高速发展，纯计算能力的重要性已经慢慢降低，程序设计课程的目的更加注重计算思维（Computational Thinking，CT）的训练。

计算思维是什么？

计算思维是一种使用计算机的逻辑来解决问题的思维。培养计算思维包括 4 个部分，分别是分解（Decomposition）、模式识别（Pattern Recognition）、模式概括与抽象（Pattern Generalization and Abstraction）以及算法（Algorithm）。下面我们来一一讲解它们具体是什么。

分解

将一个复杂的问题分割成许多小问题即为分解。

模式识别

在将一个复杂的问题分解之后，我们常常可以发现小问题中有共同的属性以及相似之处，在计算思维中，这些属性被称为模式（Pattern）。模式识别是指在一组数据中找出特征（Feature）或规则（Rule），用于对数据进行识别与分类，以作为决策判断的依据。

模式概括与抽象

模式概括与抽象在于过滤以及忽略掉不必要的特征，让我们可以集中在重要的特征中，这样有助于将问题抽象化。通常这个过程开始会收集许多数据和资料，通过模式概括与抽象把无助于解决问题的特性和模式去掉，留下相关的以及重要的属性，直到我们确定一个通用的问题以及建立解决这个问题的规则。

算法

算法是计算思维 4 个基石的最后一个，不但是人类使用计算机解决问题的技巧之一，也是程序设计的精髓。算法常出现在规划和程序设计的第一步，因为算法本身就是一种计划，每一条指令与每一个步骤都是经过规划的，在这个规划中包含解决问题的每一个步骤和每一条指令。

算法的条件

了解完算法的定义后，我们来看看算法必须符合的 5 个条件。

算法的特性	内容与说明
输入(Input)	0 个或多个输入数据，这些输入必须有清楚的描述或定义
输出(Output)	至少会有一个输出结果，不能没有输出结果
明确性(Definiteness)	每一条指令或每一个步骤必须是简介明确的
有限性(Finiteness)	在有限步骤后一定会结束，不会产生无限循环
有效性(Effectiveness)	步骤清楚且可行，只要时间允许，用户就可以用纸笔计算而求出答案

PS：算法和过程是有区别的，过程不一定要满足算法有限性的要求，例如操作系统或者计算机运行的过程除非宕机，否则永远在等待循环（Waiting Loop）中，这就违反了算法 5 大条件中的有限性。

时间复杂度 O(F(n))

计算机领域利用一种概量的概念来衡量算法的运行时间，称之为时间复杂度（Time Complexity）。它的详细定义如下：

在一个完全理想状态下的计算机中，我们定义 T(n) 来表示程序执行所要花费的时间，其中 n 代表数据输入量。当然，程序的运行时间（Worse Case Executing Time）或最大运行时间是时间复杂度的衡量标准，一般以 Big-Oh 表示。

在分析算法的时间复杂度时，往往用函数来表示它的成长率（Rate of Growth），其实时间复杂度是一种渐近表示法（Asymptotic Notation）。

O(f(n)) 可视为算法在计算机中所需的运行时间不会超过某一常数倍的 f(n)。也就是说，当某算法的运行时间 T(n) 的时间复杂度为 O(f(n))（读成 Big-Oh of f(n) 或 Order is f(n)）时，意思是存在两个常数 c 与 n₀ ，若 n >= n₀ ，则 T(n) <= cf(n) 。f(n) 又称为运行时间的成长率（Rate of Growth）。由于在估算算法复杂度时采取“宁可高估不要低估”的原则，因此估计出来的复杂度是算法真正所需时间的上限。

下面给个范例让懂数学的人了解一下时间复杂度的意义。

范例：

假如运行时间 T(n) = 3n^3 + 2n^2 + 5n ，求时间复杂度。解答：首先找出常数 c 与 n₀ 。当 n₀ = 0 、 c = 10 时，若 n >= n₀ ，则 3n^3 + 2n^@+5n <= 10n^# ，因此得知时间复杂度为 O(n^3) 。

事实上，时间复杂度只是执行次数的一个概略的量度，并非真实的执行次数。而 Big-Oh 则是一种用来表示最坏运行时间的表现方式，也是常用于描述时间复杂度的渐近式表示法。以下是常见的一些 Big-Oh ：

Big-Oh	特色与说明
O(1)	常数时间（Constant Time），表示算法的运行时间是一个常数倍
O(n)	线性时间（Linear Time），表示执行的时间会随着数据集合的大小而线性增长
O(log₂n)	次线性时间（Sub-Linear Time），成长速度比线性时间慢，比常数时间快
O(n^2)	平方时间（Quadratic Time），算法的运行时间会呈二次方增长
O(n^3)	立方时间（Cubic Time），算法的运行时间会呈三次方增长
O(2ⁿ)	指数时间（Exponential Time），算法的运行时间会呈 2 的 n 次方增长。例如，解决 Nonpolynomial Problem 问题算法的时间复杂度为 O(2ⁿ)
O(nlog₂n)	线性乘对数时间，介于线性和二次方增长的中间模式

n >= 16 时，时间复杂度的优劣比较关系如下：

O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n^2) < O(n^3) < O(2ⁿ)

结构化程序设计

在传统程序设计的方法中，主要以由下而上与由上而下方法为主。所谓由下而上，是指程序员将整个程序需求中最容易的部分先编写，再逐步扩大来完成整个程序。由上而下则是将整个程序需求从上而下、由大到小逐步分解成较小的单元，或称为模块（Module），这样使得程序员针对各模块分别开发，不但可以减轻设计者的负担、可读性较高，也便于日后维护。

通常结构化程序设计具有 3 种控制流程，对于一个结构化程序，无论其结构如何复杂，都可以利用这 3 种基本控制流程来加以表达：

[顺序结构] 逐步编写程序语句
[选择结构] 根据某些条件进行逻辑判断
[重复结构] 根据某些条件决定是否重复执行某些程序语句