Think together · Start with a little story
The robot keeps recalculating the total number of pages from the previous week. The girl asks, “Could you save a result after calculating it?”
Lay out the process
- Observe firstFind what repeats most
- Reuse resultsSave running totals
- Check correctnessCompare with the original method
- MeasureTime the same input
Find the real bottleneck first, then reduce repeated work or choose a better algorithm.
Optimization also has costs: caching and preprocessing use memory and take time, and saved results must still be valid when the input changes.
01What should you do first when a program is slow?
Do not rush to “add all kinds of optimizations.”
The cause may be a slow algorithm, I/O, memory access, repeated computation, or something else.
02Method 1: Reduce repeated computation
If the same result is calculated repeatedly, consider storing it for reuse.
Prefix sums are a classic example: spend O(n) on preprocessing, then answer each range-sum query in O(1).
03Method 2: Choose a more suitable algorithm
Linear search
O(n)
Binary search on ordered data
O(log n)
Binary search works only when its required conditions are met.
04Method 3: Choose a different data structure
If your program repeatedly removes the front item, a suitable queue is more natural than repeatedly shifting an entire array.
If you need to look up values by key quickly, you might consider a hash table.
05Method 4: Prune impossible search paths
During a search, if you know a branch cannot possibly lead to an answer, there is no need to explore it further.
This idea is called pruning.
06Method 5: Reduce unnecessary I/O
In programming problems, reading one character at a time or frequently flushing output may also slow a program down.
However, optimize I/O when it is truly a bottleneck; do not apply a template blindly.
07Why not just “write shorter code”?
Fewer lines of code do not mean less work during execution.
std::sort(a.begin(), a.end());It is only one line, but a complex algorithm still runs inside it.
08How can you tell whether an optimization really helped?
Complexity analysis
Check the growth trend.
Correctness tests
Do not change the answer just to make the program faster.
Measurement
Use timing or a profiler in a realistic environment.
09What is the most important optimization principle?
What have you learned?
- Find the bottleneck before optimizing.
- Reducing repeated computation or changing the algorithm or data structure may help.
- Pruning can reduce wasted search work.
- Shorter code is not necessarily faster code.
- Optimization must preserve correctness and be checked with analysis and measurement.
Topic complete: The next topic is “Problem-Solving Strategies for Programming Contests.”
Your turn to try
Would changing only a variable name make one million repeated additions disappear?
Ready? Open to see the explanation
No. You need to change the actual amount of work or the bottleneck in the implementation, then verify it under the same test conditions.