3.17 Algorithmic Efficiency 算法效率

There exist problems that computers cannot solve, and even when a computer can solve a problem, it may not be able to do so in a reasonable amount of time.

• 存在计算机无法解决的问题，即使计算机能够解决一个问题，它也可能无法在合理的时间内做到。

核心要点 Core Points

1. A "problem" is a general description of a task that can or cannot be solved algorithmically, and an "instance" of a problem as including specific input (e.g., sorting is a problem; sorting the list (2,3,1,7) is an instance).

   • "问题"是可以或不能通过算法解决的任务的一般描述，"问题实例"包括特定输入（例如，排序是一个问题；排序列表(2,3,1,7)是一个实例）。

2. A "decision problem" is one that has a yes/no answer (e.g., path from A to B?), while an "optimization problem" is one that involves finding the "best" solution (e.g., shortest path from A to B?).

   • "决策问题"是有是/否答案的问题（例如，从A到B的路径？），而"优化问题"是涉及找到"最佳"解决方案的问题（例如，从A到B的最短路径？）。

3. "Efficiency" is an estimation of computational resources used by an algorithm, typically expressed as a function of input size.

   • "效率"是算法使用的计算资源的估计，通常表示为输入大小的函数。

4. An algorithm's efficiency is determined through formal or mathematical reasoning.

   • 算法的效率通过形式或数学推理确定。

5. An algorithm's efficiency can be informally measured by determining the number of times a statement or group of statements executes.

   • 算法的效率可以通过确定语句或语句组执行的次数来非正式地测量。

6. Different correct algorithms for the same problem can have different efficiencies.

   • 同一问题的不同正确算法可以有不同的效率。

7. Algorithms with a polynomial efficiency or slower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time. Algorithms with exponential or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.

   • 具有多项式效率或更慢（常数、线性、平方、立方等）的算法被认为在合理的时间内运行。具有指数或阶乘效率的算法是在不合理时间内运行的算法例子。

8. Some problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for solving them. In these cases, approximate solutions are sought.

   • 某些问题无法在合理的时间内解决，因为没有解决它们的有效算法。在这些情况下，寻求近似解决方案。

9. A heuristic is an approach to a problem that produces a solution that is not guaranteed to be optimal but may be used when techniques that are guaranteed to always find an optimal solution are impractical.

   • 启发式是解决问题的方法，它产生的解决方案不保证是最优的，但当保证总是找到最优解决方案的技术不实用时可以使用。

学生活动 Student Activities

1. For determining the efficiency of an algorithm:
   • 对于确定算法的效率：
   • Explain the difference between algorithms that run in reasonable time and those that do not.
     • 解释在合理时间内运行的算法与不在合理时间内运行的算法之间的区别。
   • Identify situations where a heuristic solution may be more appropriate.
     • 识别启发式解决方案可能更合适的情况。

相关资源 Related Resources

• AP CSP Exam Reference Sheet
  • AP CSP考试参考表