Algorithms · 算法
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| algorithm/ˈælɡərɪθəm/ | 算法 | suàn fǎ |
| flowchart/ˈfləʊtʃɑːt/ | 流程图 | liú chéng tú |
| pseudocode/ˈsuːdəʊkəʊd/ | 伪代码 | wěi dài mǎ |
| tracing/ˈtreɪsɪŋ/ | 追踪 | zhuī zōng |
| binary search/ˈbaɪnəri sɜːtʃ/ | 二分查找 | èr fēn chá zhǎo |
| linear search/ˈlɪnɪə sɜːtʃ/ | 线性查找 | xiàn xìng chá zhǎo |
| efficiency/ɪˈfɪʃənsi/ | 效率 | xiào lǜ |
Say which inputs the procedure must handle
- An algorithm 算法 describes unambiguous steps for a task. A procedure solving a stated finite task must terminate and give the correct result for every allowed input.
- A successful trace on one input shows that case, not a proof for all inputs. Boundary and empty-input cases can expose errors that a typical example misses.
Which are required for a sequence of steps to be an algorithm? Choose all that apply.
A procedure solving the stated finite task needs unambiguous steps, correct results and termination on allowed inputs. Pseudocode and flowcharts are representations, not requirements to use a particular programming language.
Represent choices and updates clearly
- A flowchart 流程图 uses a decision diamond, process rectangle, input/output parallelogram and start/stop terminal, connected by directed flow arrows.
- Pseudocode 伪代码 describes the steps without requiring one implementation language. State assignment meaning, index origin, loop bounds and branch conditions before tracing.
Match each flowchart shape to what it means.
Use process rectangles, decision diamonds and start/stop terminals as given; input/output is normally shown by a parallelogram. Label decision branches and flow directions.
Record the actual variable values
- Tracing 追踪 follows the stated updates in order. A temporary variable may preserve a value that would otherwise be overwritten.
- Show low, high, middle and compared value for a binary search; show every changed variable for an arithmetic loop. Judge what the procedure does, not only its intended purpose.
A specified binary-search convention. Use zero-based inclusive bounds and floor of their average for the middle. Searching for 7 in [1,3,5,7,9,11] compares index 2/value 5, index 4/value 9, then index 3/value 7. The comparison count is three under this convention.
Linear against binary search · 线性搜索对比二分搜索
Halving beats checking one at a time, and the gap widens with the list.
Using zero-based inclusive bounds and floor((low+high)/2), how many comparisons does binary search use to find 7 in [1,3,5,7,9,11]?
Middle indices are 2, 4, then 3, with values 5, 9 and 7. Three comparisons under the specified convention.
Compare work under its assumptions
- A linear search 线性查找 can stop early but may inspect all n items. A binary search 二分查找 repeatedly halves a sorted search range and needs consistent bound updates.
- Efficiency 效率 describes how required work scales with input size under a defined model. Sorting first has its own cost; an unsorted input cannot rely on binary search's ordering guarantee.
For an already sorted million-item list, approximately how many middle-value comparisons can binary search need in the worst case?
Each comparison halves the remaining search range; about 20 comparisons suffice for a million ordered items. This excludes any cost of sorting beforehand.
A binary search works on an unsorted list, just more slowly.
Without the required ordering, discarding a half can miss a present item. Some cases may happen to succeed, but correctness is not guaranteed.
Check zero and the last allowed index. Sheet 4.4 examines a sum loop using i less than n, which misses the last term. Its Euclidean trace also explains termination: each positive divisor is replaced by a smaller nonnegative remainder until zero is reached.