计算思维与问题求解

一个搜索(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。)

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$) 代价),若你搜索许多次就值得。

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]。

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

ADT 可以从其他 ADT 构建,而不只是从数组:一个队列从两个栈;一个栈从一个链表(push = 在头部前置一个节点(node));一个队列从一个带头和尾指针(pointers)的链表;一棵二叉树(binary tree)从带两个孩子指针的节点;一个字典(dictionary)存储键→值对(常在一个哈希表上)。这样分层分离关注点——使用该 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$ 次——这就是为什么增长的阶,而不是原始速度,决定规模上的赢家。

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,二分查找、归并排序)和嵌套数据。当它不合适时,一个循环通常更清爽。

Tracing a recursive call

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

Risks

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

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

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

• 把每个算法匹配到它的大O:线性查找 $O(n)$、二分查找 $O(\log n)$、冒泡/插入 $O(n^2)$、好的排序 $O(n \log n)$。
• 二分查找需要一个已排序的列表并每步把搜索空间折半。
• 一个递归例程需要一个基本情形和一个对它自己的调用;解释深度递归如何使调用栈溢出。
• 当被要求时用一个表格追踪一个排序或搜索,显示每一趟。