计算思维与问题求解

一个搜索(search)在一个集合(常常是一个数组(array))中找一个目标值并返回它的位置,或"未找到"。

Linear search

一个线性查找(linear search)从头走到尾,把每个元素与目标比较:

FOR i ← 1 TO n
    IF A[i] = target THEN RETURN i
NEXT i
RETURN -1   // not found

不需要准备,所以它在任何列表上都能用。最坏情况 O($n$)(目标在末端或不存在);最好情况 1 次比较。在未排序的数据或小列表上用它。(返回的 -1 是一个哨兵值——一个表示"未找到"的不可能位置;调用者测试 IF result = -1。)

考试的版本。 试卷 3 要你补全用标志和 WHILE 循环写的线性查找,试卷 4 要你写一个返回下标或计数的函数。两者都像这样:

FUNCTION LinearSearch(Data : ARRAY OF INTEGER, Target : INTEGER) RETURNS INTEGER
    DECLARE Index, Count : INTEGER
    Count ← 0
    FOR Index ← 1 TO 100
        IF Data[Index] = Target THEN
            Count ← Count + 1
        ENDIF
    NEXT Index
    RETURN Count          // Target 出现的次数;0 表示未找到
ENDFUNCTION

要在第一个匹配处停止,改用 WHILE Index <= 100 AND NOT Found 循环,设置 Found ← TRUE 并记住下标。分数在于遍历每个元素的循环、比较,以及值不存在时返回什么。

Binary search

一个二分查找(binary search)需要数据已排序。看中间元素;若它是目标,完成;若目标更小,搜索左半,否则右半——每次把范围折半:

low ← 1
high ← n
WHILE low <= high DO
    mid ← (low + high) DIV 2
    IF A[mid] = target THEN RETURN mid
    IF A[mid] < target THEN
        low ← mid + 1
    ELSE
        high ← mid - 1
    ENDIF
ENDWHILE
RETURN -1

最坏情况 O($\log_{2} n$)——对一百万项,约 20 次比较。在大的已排序数组上比线性查找快得多,但你必须先排序(一个一次性的 O($n \log n$) 代价),若你搜索许多次就值得。

"说明二分查找的必要条件。" 数据必须有序(按所查找的键升序或降序排列)。"描述如何进行二分查找"(三分):(1) 找到列表(或当前范围)的中间项并与目标比较;(2) 若匹配则查找结束;若目标更小,对下半部分重复,若更大则对上半部分重复;(3) 不断折半范围,直到找到该项或范围为空,即它不存在。

带边界和标志的考试版本,是被要求补全算法时要复现的:

DECLARE Lower, Upper, Mid : INTEGER
DECLARE Found : BOOLEAN
Lower ← 0
Upper ← 99
Found ← FALSE
WHILE Lower <= Upper AND NOT Found
    Mid ← (Lower + Upper) DIV 2
    IF Names[Mid] = Target THEN
        Found ← TRUE
    ELSE
        IF Names[Mid] < Target THEN
            Lower ← Mid + 1
        ELSE
            Upper ← Mid - 1
        ENDIF
    ENDIF
ENDWHILE
IF Found THEN OUTPUT Mid ELSE OUTPUT "Not found" ENDIF

"解释性能如何随项数变化。" 每次比较把剩余项数折半,所以最大比较次数约为 $\log_{2} n$:列表规模加倍只多一次比较。这是 O($\log n$)。"比较线性查找和二分查找":线性查找最多需要 $n$ 次比较(O($n$)),平均为其一半,但对未排序数据也能用;二分查找最多需要 $\log_{2} n$ 次(O($\log n$)),对大列表快得多,但数据必须先排序,并且必须能直接访问中间项(数组,而不是链表)。对 $1000$ 项:$1000$ 次对 $10$ 次比较。

Bubble sort

一个冒泡排序(bubble sort)反复走过数组,交换顺序错误的相邻对,所以最大的每趟"冒泡"到末端:

FOR pass ← 1 TO n - 1
    swapped ← FALSE
    FOR i ← 1 TO n - pass
        IF A[i] > A[i + 1] THEN
            temp ← A[i]
            A[i] ← A[i + 1]
            A[i + 1] ← temp
            swapped ← TRUE
        ENDIF
    NEXT i
    IF swapped = FALSE THEN EXIT FOR   // already sorted
NEXT pass

最好情况 O($n$)(已排序,带早退);平均/最坏 O($n^{2}$)。简单但对大的 $n$ 慢。

Insertion sort

一个插入排序(insertion sort)从左边构建一个已排序的前缀,通过把较大的向右移把每个新元素插入位置:

FOR i ← 2 TO n
    key ← A[i]
    j ← i - 1
    WHILE j >= 1 AND A[j] > key DO
        A[j + 1] ← A[j]
        j ← j - 1
    ENDWHILE
    A[j + 1] ← key
NEXT i

最好情况 O($n$)(已排序);最坏 O($n^{2}$)。适合小或近乎已排序的数组。它原地(in place)排序并且是稳定的(stable,保持相等元素的顺序)。

Tracing a sort

一个常见的任务是显示每一次外趟之后的数组。对 [D, T, H, R] 用插入排序:趟 1(key T)无变化;趟 2(key H)→ [D, H, T, R];趟 3(key R)→ [D, H, R, T]。

从头写一个排序。 "写出把 DataArray[1:1000] 升序排序的伪代码"用带提前退出标志的完整冒泡排序或插入排序作答,带声明和缩进;只要对每种输入都正确,两者都得满分:

DECLARE Pass, Index, Temp : INTEGER
DECLARE Swapped : BOOLEAN
Pass ← 1
REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO 1000 - Pass
        IF DataArray[Index] > DataArray[Index + 1] THEN
            Temp ← DataArray[Index]
            DataArray[Index] ← DataArray[Index + 1]
            DataArray[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
    Pass ← Pass + 1
UNTIL Swapped = FALSE OR Pass = 1000

要降序就把 > 改成 <;要按某个字段排序记录或二维数组,比较该字段但交换整条记录(或每一列)。被要求写一个"完成与给定冒泡排序相同任务"的插入排序时,保持同样的数组名和方向,复现上面的插入排序,若为降序则把比较反过来。

"描述排序性能受数据影响的两种方式"(两分)。 (1) 项目的数量:$O(n^{2})$ 的排序对两倍的项目要花四倍的时间。(2) 数据已经有序到什么程度:带标志的冒泡排序或插入排序对已排序的数据一趟就结束($O(n)$),对逆序数据做的工作最多;交换次数取决于有多少对是乱序的。(也可接受:取值范围或重复值的数量,以及项目是否是移动代价高的大记录。)冒泡排序和插入排序在最坏和平均情况下都是 O($n^{2}$),最好情况 O($n$);快速排序和归并排序是 O($n \log n$),这就是它们用于大数据的原因。

主题 10 的抽象数据类型(ADT)出现在许多算法内部:一个栈(stack)驱动深度优先遍历和撤销;一个队列(queue)驱动广度优先遍历和打印排序;一个链表(linked list)让数据增长和收缩。

ADT 可以从其他 ADT 构建,而不只是从数组:一个队列从两个栈;一个栈从一个链表(push = 在头部前置一个节点(node));一个队列从一个带头和尾指针(pointers)的链表;一棵二叉树(binary tree)从带两个孩子指针的节点;一个字典(dictionary)存储键→值对(常在一个哈希表上)。这样分层分离关注点——使用该 ADT 的算法不必知道它如何构建。

考试要你描述和实现的 ADT

栈(后进先出):项目在同一端即栈顶加入(压入)和移除(弹出);指针 TopOfStack 保存栈顶项的下标。用一个数组和这一个指针实现:压入检查栈未满、递增指针并存入项目;弹出检查栈非空、返回栈顶项并递减指针。

FUNCTION Push(Item : INTEGER) RETURNS BOOLEAN
    IF TopOfStack = 9 THEN RETURN FALSE ENDIF      // 已满(数组 0 到 9)
    TopOfStack ← TopOfStack + 1
    StackData[TopOfStack] ← Item
    RETURN TRUE
ENDFUNCTION
FUNCTION Pop() RETURNS INTEGER
    IF TopOfStack = -1 THEN RETURN -1 ENDIF        // 已空
    TopOfStack ← TopOfStack - 1
    RETURN StackData[TopOfStack + 1]
ENDFUNCTION

队列(先进先出):项目在队尾加入(入队)、从队首离开(出队);两个指针和一个计数。在线性队列中队首指针沿数组前移,开头的空间被浪费;循环队列(circular queue)用 MOD 让两个指针绕回,使每个单元都被重用。

FUNCTION Enqueue(Item : STRING) RETURNS BOOLEAN
    IF Count = 6 THEN RETURN FALSE ENDIF            // 已满
    Rear ← (Rear + 1) MOD 6
    QueueArray[Rear] ← Item
    Count ← Count + 1
    RETURN TRUE
ENDFUNCTION
FUNCTION Dequeue() RETURNS STRING
    IF Count = 0 THEN RETURN "" ENDIF               // 已空
    DECLARE Item : STRING
    Item ← QueueArray[Front]
    Front ← (Front + 1) MOD 6
    Count ← Count - 1
    RETURN Item
ENDFUNCTION

链表:一串节点,每个保存一个数据项和指向下一个节点的指针;起始指针给出第一个节点,空指针(0 或 $-1$)结束链表。用数组实现时,两个平行数组保存数据和指针,未用的单元串成空闲列表(free list),使插入时知道把新节点放在哪里。

FUNCTION FindInList(Target : STRING) RETURNS INTEGER   // 下标,不存在则为 0
    DECLARE Current : INTEGER
    Current ← Start
    WHILE Current <> 0
        IF Data[Current] = Target THEN RETURN Current ENDIF
        Current ← Pointer[Current]
    ENDWHILE
    RETURN 0
ENDFUNCTION

要插入有序链表:取第一个空闲单元(NewNode ← FreeList,FreeList ← Pointer[FreeList]),存入项目,然后用 Previous 和 Current 指针遍历链表直到 Data[Current] > Item 或到末尾;设 Pointer[NewNode] ← Current 和 Pointer[Previous] ← NewNode(若排在最前则 Start ← NewNode)。要删除,把前一个节点重新链接到被删节点之后,并把该单元归还空闲列表。

二叉树:一个根节点,每个节点保存数据、一个指向较小值子树的左指针和一个指向较大值子树的右指针。实现为二维数组(或三个一维数组)Tree[Index, 0..2],存左指针、数据、右指针,加一个根指针和一个下一空闲指针。

FUNCTION FindInTree(Target : INTEGER) RETURNS INTEGER   // 下标,不存在则为 -1
    DECLARE Current : INTEGER
    Current ← Root
    WHILE Current <> -1
        IF Tree[Current, 1] = Target THEN RETURN Current ENDIF
        IF Target < Tree[Current, 1] THEN
            Current ← Tree[Current, 0]      // 向左
        ELSE
            Current ← Tree[Current, 2]      // 向右
        ENDIF
    ENDWHILE
    RETURN -1
ENDFUNCTION

要插入:把项目存入下一个空闲节点,两个指针都设为 $-1$;若树为空则令它为根;否则从根向下,按比较向左或向右,直到要跟随的指针为 $-1$,把该指针设为新节点。用一个 ADT 构建另一个 ADT:栈是压入和弹出都在起始端进行的链表;队列是带起始和末尾指针的链表;队列可以用两个栈构成(压入一个,从另一个弹出,第二个为空时把全部搬过去);二叉树的节点是由指针链接的记录或对象,所以它由节点的链式结构构成。要说明新 ADT 的哪些操作对应旧 ADT 的哪些操作。

Time complexity

时间复杂度(time complexity)是运行时间如何随输入大小 $n$ 增长,写成大O表示法(Big-O notation,主导项):O(1) 常数、O($\log n$) 二分查找、O($n$) 线性查找、O($n \log n$) 好的排序、O($n^{2}$) 冒泡/插入排序。较小的阶在规模上更好,即使另一个算法对小 $n$ 更快。

具体地说:要排序一百万项,一个 $O(n \log n)$ 排序在不到一秒内完成,而一个 $O(n^{2})$ 排序可能花几分钟。

例题。 一个已排序的列表容纳 $1000$ 项。每个搜索在最坏情况下需要多少次比较?

一个线性查找一次检查一项,所以它可能需要多达 $1000$ 次比较——这是 $O(n)$。一个二分查找每步把列表折半,所以它最多需要 $\lceil \log_2 1000 \rceil = 10$ 次比较——这是 $O(\log n)$。把列表翻倍到 $2000$ 项只给二分查找加一次比较,但给线性查找加多达另外 $1000$ 次——这就是为什么增长的阶,而不是原始速度,决定规模上的赢家。

描述一个阶。 *O(1):*时间恒定,与项数无关(压栈、读数组元素)。*O($\log n$):*时间随项数的对数增长,所以数据加倍只多一个固定的步骤(二分查找)。*O($n$):*时间与项数成比例增长(线性查找,遍历一遍列表)。*O($n \log n$):*比线性稍差(高效排序)。*O($n^{2}$):*时间随项数的平方增长,所以数据加倍时间变为四倍(冒泡和插入排序)。"说出对 Names[0:99] 二分查找的大 O"答 $O(\log n)$,"描述其含义"如上;大 O 度量时间或内存如何伸缩,而不是实际时间。

Space complexity

空间复杂度(space complexity)是需要的额外内存。冒泡和插入排序用 O(1) 额外(原地);归并排序用 O($n$);递归用与它的深度成正比的栈内存。常常有一个时间–内存权衡。

Other criteria

简单性(更容易编码和维护)、稳定性,以及自适应性(在近乎已排序的数据上更快)。正确的算法取决于数据和约束。

递归算法用递归(recursion):例程用同一问题的一个更小的版本调用它自己,直到一个基本情形(base case)结束这条链。它有两部分:基本情形(小到能直接解决——没有它递归永不停止)和递归情形(recursive case,减小输入并调用它自己)。

阶乘(factorial):

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
    IF n = 0 OR n = 1 THEN
        RETURN 1
    ELSE
        RETURN n * Factorial(n - 1)
    ENDIF
ENDFUNCTION

递归对自相似的问题是自然的:树、分治(divide-and-conquer,二分查找、归并排序)和嵌套数据。当它不合适时,一个循环通常更清爽。

"描述递归是什么意思"(两分)。 用自身定义的函数或过程:它在自己的函数体内调用自己,每次处理一个更小的问题版本,直到到达基本情形。 "说出递归的三个基本特征":(1) 一个基本情形(停止条件),不再调用而直接返回一个值;(2) 一个一般情形(general case),其中例程调用自身;(3) 每次调用使问题更接近基本情形(参数减小),从而递归终止。有些评分方案还加上:值在调用解退时返回。

"描述递归何时有益,并举例。" 当问题天然地由其更小版本定义,使得递归解比循环更短、更清晰、更接近数学定义时:阶乘或斐波那契数、二分查找、遍历二叉树、归并排序或快速排序,以及处理文件夹套文件夹这样的嵌套结构。当深度很大(栈可能溢出)或同一子问题被计算多次(朴素的斐波那契)时,它是糟糕的选择。

Tracing a recursive call

对 Factorial(4):调用往下走到 Factorial(1)=1,然后展开往上乘回来:2*1=2、3*2=6、4*6=24。最终结果 24。在一个栈上跟踪每个待处理的调用。

例题。 下面的函数没有说明。追踪 Unknown(3, 5),说出它的输出和返回值。

FUNCTION Unknown(BYVAL X, BYVAL Y : INTEGER) RETURNS INTEGER
    IF X < Y THEN
        OUTPUT X + Y
        RETURN Unknown(X + 1, Y - 1) + 1
    ELSE
        RETURN 0
    ENDIF
ENDFUNCTION

调用 1:$X = 3, Y = 5$:$3 < 5$,输出 8,调用 Unknown(4, 4)。调用 2:$4 < 4$ 为假,返回 0。解退:调用 1 返回 $0 + 1 = 1$。输出 8,返回值 1。把追踪写成每次调用一行的表(参数、条件、输出、返回什么),并从最深的调用向上做返回:那就是评分方案要找的解退。

例题(斐波那契)。 Fib(n) 在 n < 2 时返回 n,否则返回 Fib(n - 1) + Fib(n - 2)。求 Fib(5)。

Fib(5) = Fib(4) + Fib(3);Fib(4) = Fib(3) + Fib(2);Fib(3) = Fib(2) + Fib(1);Fib(2) = Fib(1) + Fib(0) = 1 + 0 = 1。所以 Fib(3) = 1 + 1 = 2,Fib(4) = 2 + 1 = 3,Fib(5) = 3 + 2 = 5。基本情形被到达许多次(Fib(2) 被计算三次),这就是这个版本慢的原因:对 $n = 5$ 它做 15 次调用,$n$ 每增加 1 调用数大约翻倍。

把递归改成迭代。 每个递归例程都可以用循环改写,占用更少内存且更快:保存一个累积结果,从基本情形向上循环。循环版的阶乘:

FUNCTION Factorial(N : INTEGER) RETURNS INTEGER
    DECLARE Result, Count : INTEGER
    Result ← 1
    FOR Count ← 2 TO N
        Result ← Result * Count
    NEXT Count
    RETURN Result
ENDFUNCTION

被要求把递归的插入排序或查找改成迭代版本时,用一个对递归所步进的下标的循环取代自调用,并把基本情形变成循环的退出条件。

Risks

• 若错过基本情形则无限递归——用一个栈溢出(stack overflow)崩溃。
• 深度递归的高内存使用。
• 若它重复工作则慢(朴素的斐波那契是指数的——用一个循环或记忆化(memoisation))。

递归需要每个调用有它自己的副本,包括它的参数(parameters)和局部变量(local variables)。编译器把这些保存在调用栈(call stack)上。对每个调用它压入一个栈帧(stack frame),容纳参数、局部变量和返回地址(return address,在调用者中在哪里恢复)。当函数返回时,返回值被交回、帧被弹出,而控制在返回地址恢复。

因为每个调用有它自己的帧,递归调用不会践踏彼此的变量。栈对深度递归可能变得很大,这就是为什么非常深的递归可能使它溢出。这是用于普通(非递归)调用的同一个调用-返回机制——没有特殊的"递归机制"。

"解释为什么栈适合实现递归"(三分)。 每次递归调用必须保存它的返回地址(return address)、参数和局部变量,而各调用以与发起相反的顺序完成(最后发起的调用最先结束),这正是栈的后进先出行为:每个新调用压入一个帧,每次返回弹出最近的帧,恢复调用者的状态并告诉它从哪里继续。这就是编译器翻译递归代码时的工作:它在每次调用时生成压入栈帧、每次返回时生成弹出,帧随着结果的返回而解退。

定义题按固定措辞评分。准确学会这些,只给一个答案。

• 查找:线性查找不需要顺序,O($n$);二分查找需要已排序数组,每次折半,O($\log n$)。两个算法都要熟记,包括边界和标志。
• 排序:带交换标志的冒泡排序,用一个键把较大项右移的插入排序;两者最坏都是 O($n^{2}$),对已排序数据是 O($n$)。性能取决于项数和有序程度。
• ADT 实现就是指针簿记:一个栈顶指针;带 MOD 的队首、队尾和计数;起始指针、指针和空闲列表;带左右指针的根。总要检查满和空。
• 大 O 关乎伸缩:常数、对数、线性、平方。对二分查找要说"数据加倍多一次比较"。
• 递归:基本情形、一般情形、向基本情形推进;当问题用自身定义时有益;栈保存返回地址和变量,因为调用以相反顺序返回。用表格追踪,从最深的调用解退。

常见错误

• 对未排序数据或链表用二分查找;以及把 Lower ← Mid 而不是 Mid + 1,导致死循环。
• 冒泡排序的内循环每趟都跑到数组末尾,或不用临时变量就交换。
• 压入或入队不检测满,弹出或出队不检测空。
• 在循环队列中移动队首指针不用 MOD,或把队首 = 队尾一律当作空。
• 通过移动数组内容来插入链表;只有指针改变。
• 递归函数没有基本情形,或其递归调用没有让问题变小。
• 追踪递归调用但忘记在返回途中加上待做的工作。
• 用"因为它快"回答"为什么用栈";理由是返回的后进先出顺序。