📚 The Concept of a Limit in Computation | 计算中极限的概念
In A-level Computer Science, the word 'limit' appears in two important senses: a mathematical limit that describes how an algorithm's resource use grows, and a computational limit that describes whether a problem can be solved at all. Both ideas shape how computer scientists choose algorithms and understand what machines can and cannot do.
在 A-level 计算机科学中，“极限”一词有两个重要含义：一是数学极限，用于描述算法资源消耗的增长方式；二是计算极限，用于描述一个问题是否从根本上可解。这两个概念共同影响计算机科学家如何选择算法，并理解机器能做什么、不能做什么。
1. Defining a Limit in Computing | 计算中极限的定义
In computing, a limit is a boundary on performance or solvability. A mathematical limit asks what happens to a ratio or quantity as the input size n becomes arbitrarily large. A computational limit asks whether any algorithm can solve a given problem within finite resources.
在计算中，极限是对性能或可解性的边界。数学极限研究当输入规模 n 任意增大时，某个比值或数量会趋近于什么；计算极限则研究是否存在任何算法能在有限资源内解决给定问题。
These limits are not just theoretical. They decide whether a program will finish before a deadline, whether a search can scale to a million users, and whether a problem is worth attempting with a computer at all.
这些极限并非只是理论问题。它们决定程序能否在截止时间前运行完毕、搜索能否扩展到百万用户，以及某个问题是否值得用计算机尝试解决。
2. Limits of Algorithms: Time and Space | 算法的极限：时间与空间
Every algorithm consumes two key resources: time, usually measured by the number of elementary steps, and space, usually measured by the number of memory cells. The limit of an algorithm describes how these resources grow as the input size n increases.
每种算法都会消耗两种关键资源：时间，通常用基本操作步数衡量；空间，通常用内存单元数量衡量。算法的极限描述这些资源如何随输入规模 n 的增大而增长。
For example, a linear search through n items takes at most n comparisons in the worst case. As n tends to infinity, the worst-case cost grows without bound, but it grows steadily rather than explosively.
例如，对 n 个元素进行线性搜索，最坏情况下最多需要 n 次比较。当 n 趋于无穷时，最坏情况成本无界增长，但它是线性稳定增长，而不是爆炸式增长。
3. Asymptotic Notation and Limits | 渐近记号与极限
Asymptotic notation expresses the limiting behaviour of resource functions. Big-O gives an upper bound, Big-Omega gives a lower bound, and Big-Theta gives a tight bound. These notations ignore constant factors and focus on the dominant term as n grows.
渐近记号描述资源函数的极限行为。大O 给出上界，大Ω 给出下界，大Θ 给出紧界。这些记号忽略常数因子，专注于 n 增大时占主导地位的项。
ions and the ratio f(n)/g(n) tends to a positive constant c as n → ∞, then f(n) = Θ(g(n)).
一个形式化的极限联系是：如果 f(n) 和 g(n) 为正函数，且当 n → ∞ 时比值 f(n)/g(n) 趋于正常数 c，则 f(n) = Θ(g(n))。
If lim (n → ∞) f(n) / g(n) = c > 0, then f(n) = Θ(g(n))
该公式将渐近等价与数学极限直接关联，帮助证明两个函数增长阶相同。
4. Big-O as an Upper Bound | 大O作为上界
≥ n₀, f(n) ≤ c × g(n). This means f does not grow faster than g, up to a constant factor.
大O 记号描述最坏情况资源上限。如果存在常数 c 和 n₀，使得对所有 n ≥ n₀ 都有 f(n) ≤ c × g(n)，则称 f(n) = O(g(n))。这意味着 f 的增长速度不超过 g，至多相差一个常数因子。
²) because for large n, the term 3n² dominates, and we can choose c = 4 and a suitable n₀.
例如，3n² + 5n + 10 = O(n²)，因为当 n 很大时，3n² 项占主导，我们可以选择 c = 4 和合适的 n₀ 来满足定义。
5. Polynomial vs Exponential Growth | 多项式与指数增长
A crucial limit in algorithm design is the difference between polynomial growth, such as n² or n³, and exponential growth, such as 2ⁿ. Exponential functions eventually overtake any polynomial function, no matter how large the polynomial's degree.
算法设计中一个关键极限是多项式增长（如 n² 或 n³）与指数增长（如 2ⁿ）之间的差异。指数函数最终会超过任何多项式函数，无论多项式的次数多大。
lim (n → ∞) nᵏ / 2ⁿ = 0 for any fixed k
这个极限表明指数增长本质上更快。具有指数时间的算法即使对于中等规模的输入也会变得不切实际。
Polynomial growth may be manageable for larger inputs, but exponential growth hits a practical limit very quickly. This is why computer scientists search for polynomial-time algorithms wherever possible.
多项式增长对于较大输入仍可能可控，但指数增长会很快触及实际极限。这就是计算机科学家尽可能寻找多项式时间算法的原因。
6. The Halting Problem as a Hard Limit | 停机问题作为硬极限
Some limits are not about speed but about possibility. Alan Turing proved in 1936 that the Halting Problem is undecidable: no algorithm can determine, for every program and input, whether that program will eventually halt or run forever.
有些极限与速度无关，而与可能性有关。艾伦·图灵在 1936 年证明停机问题是不可判定的：不存在一种算法能够对每一个程序和输入，判断该程序最终会停止还是永远运行。
The proof uses contradiction by constructing a program that behaves paradoxically if a halt-checker exists. This is a hard limit of computation: it cannot be overcome by faster hardware or a cleverer programming language.
证明使用反证法，构造一个在存在停机检测器时会表现矛盾的程序。这是计算的硬极限：更快的硬件或更聪明的编程语言都无法突破它。
7. Decidability and Recognisability | 可判定性与可识别性
A decision problem is decidable if there is an algorithm that always halts and returns yes or no. It is recognisable if an algorithm halts and accepts yes-instances, but may loop forever on no-instances. Decidable problems have no fundamental limit on solvability; recognisable problems have a one-sided limit.
如果存在一个算法总能停机并返回“是”或“否”，则该判定问题是可判定的。如果算法能停机并接受“是”的实例，但在“否”的实例上可能永远循环，则该问题是可识别的。可判定问题在可解性上没有根本极限；可识别问题存在单侧极限。
The Halting Problem is recognisable but not decidable: a simulator can accept when a program halts, but cannot reliably reject when it does not halt.
停机问题是可识别的但不可判定：模拟器可以在程序停机时接受，但不能在程序不停机时可靠地拒绝。
8. P, NP and the Limits of Efficient Computation | P、NP 与高效计算的极限
omial time. Every problem in P is in NP, but whether P = NP remains a major open question.
P 是能在多项式时间内求解的判定问题类。NP 是其“是”实例能在多项式时间内验证的问题类。P 中的每个问题都在 NP 中，但 P 是否等于 NP 仍然是一个重要的开放问题。
lem is in P, then P = NP, which would push back a presumed limit of efficient computation.
NP 完全问题，如布尔可满足性问题和旅行商判定问题，是 NP 中最难的问题。如果任何一个 NP 完全问题属于 P，那么 P = NP，这将突破一个假定的高效计算极限。
9. Resource Limits in Practice | 实践中的资源极限
Even when a problem is theoretically solvable, practical limits remain. Memory size, processor speed, storage capacity and network bandwidth all impose ceilings. Algorithm designers use complexity limits to predict whether a solution will scale.
即使一个问题在理论上可解，实际极限仍然存在。内存大小、处理器速度、存储容量和网络带宽都会施加上限。算法设计者利用复杂度极限来预测解决方案是否能够扩展。
For example, an O(n²) sorting algorithm may handle 10,000 items in a second, but take over two hours for 1,000,000 items. Understanding the growth limit helps choose a better O(n log n) algorithm.
例如，O(n²) 的排序算法可能在一秒内处理 10,000 个元素，但处理 1,000,000 个元素可能需要两个多小时。理解增长极限有助于选择更好的 O(n log n) 算法。
Resource limits also affect embedded systems and real-time software, where a late answer may be as bad as no answer. Meeting hard deadlines requires worst-case analysis, not just average-case optimism.
资源极限也会影响嵌入式系统和实时软件，在这些场景中，迟到的答案可能与没有答案一样糟糕。满足硬性截止时间需要最坏情况分析，而不仅仅是平均情况下的乐观估计。
10. Working with Limits in AQA Exams | AQA 考试中的极限问题
In AQA A-level Computer Science, questions on limits often ask you to compare algorithms using Big-O, interpret the halting problem, or explain why exponential algorithms become impractical. Use precise vocabulary and give short justifications.
在 AQA A-level 计算机科学中，关于极限的问题通常要求你使用大O 比较算法、解释停机问题，或说明为什么指数算法不切实际。应使用准确术语并给出简短理由。
you can state that g(n) is the smaller growth rate because the limit n³ / 2ⁿ tends to 0. This shows that for large n, the cubic algorithm is far more efficient.
比较 f(n) = 2ⁿ 和 g(n) = n³
Published by TutorHao | A-Level Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图