Algorithmic Efficiency
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| Algorithmic efficiency/ˌælɡəˈrɪθmɪk ɪˈfɪʃənsi/ | hiệu quả thuật toán |
| slow/sləʊ/ | chậm |
| steps/steps/ | bước |
| reasonable/ˈriːzənəbl/ | hợp lý |
| unreasonable/ʌnˈriːzənəbl/ | không hợp lý |
| heuristic/hjuːˈrɪstɪk/ | phương pháp heuristic |
Correct isn't always good enough
- Two algorithms can both be correct, yet one may be far better to use.
- Algorithmic efficiency 算法效率 compares algorithms by the resources they use — mainly time and memory.
- A correct-but-slow algorithm can be useless on large inputs.
- So we need a way to compare how they scale.
Algorithmic efficiency compares algorithms by:
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Efficiency is about time and memory as input grows.
Counting steps as n grows
- Estimate the number of steps 步骤 an algorithm takes as its input size $n$ grows.
- A linear search takes about $n$ steps; a binary search about $\log_2 n$; comparing every pair about $n^2$.
- As $n$ gets large, these differences become huge.
- The shape of the growth matters far more than a stopwatch.
How the running time of an algorithm grows with the input size n
How running time grows with n
Slide n and compare the curves: log n stays almost flat, n rises steadily, n² explodes. This is why we compare algorithms by how they scale, not with a stopwatch.
Match each algorithm to its rough number of steps for input size n.
Độ khó 2/5 · 140 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
These growth rates decide which algorithm scales.
Which growth is considered unreasonable as n gets large?
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Exponential growth quickly becomes far too slow.
When an exact answer is too slow, a ______ finds a good-enough solution fast.
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
A heuristic trades a perfect answer for speed.
Reasonable vs unreasonable
- We separate a reasonable 合理 running time from an unreasonable 不合理 one.
- Roughly, growth like $n$ or $n^2$ is reasonable; doubling steps per extra item (like $2^n$) is not.
- When an exact answer is too slow, use a heuristic 启发式方法 — a good-enough solution found fast.
- Not perfect, but useful when perfect is impossible in time.
A binary search of 1,000,000 sorted items needs at most about how many steps? (2^20 ≈ a million)
Độ khó 2/5 · 140 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
Because 2^20 is just over a million, ~20 halvings suffice.
If an algorithm is correct, it will always run fast enough on large inputs.
Độ khó 1/5 · 100 xu + một phần thưởng nhỏ cho lần hoàn thành đầu tiên trong ngày
False. A correct algorithm can still be too slow on large inputs; it must also finish in a reasonable time.
Too slow to use
- This is why some correct algorithms are too slow 缓慢 to run in practice on large inputs.
- Being correct is not enough — an algorithm must also finish in a reasonable time.
A million items. A linear search of 1,000,000 sorted items may take up to 1,000,000 steps. A binary search takes at most about 20, because $2^{20}$ is just over a million. On small lists the gap barely matters; on a million items, binary is the only reasonable choice.
Algorithmic efficiency compares algorithms by resources as input size $n$ grows: linear $n$, binary $\log_2 n$, all-pairs $n^2$. Growth like $n$ or $n^2$ is reasonable; $2^n$ is unreasonable (use a heuristic). A correct algorithm that is too slow on large inputs is not good enough.