Неформальный анализ времени выполнения

Counting the work

• We measure a program's run time 运行时间 by how many times its key statements run.
• Not seconds (those vary by machine) — a count of operations as the input grows.
• More operations for the same input size → slower algorithm.
• This lets us compare algorithms fairly, independent of hardware.

A single loop: about n

• A loop over n items runs its body about n times.
• Double the input → about double the work. This is linear 线性 growth.
• Summing an array, searching a list one-by-one: all about n steps.
• Written informally as "order n."

How the running time grows with the number of elements n

A nested loop: about n²

• A nested loop over n items runs its inner body about n × n = n² times.
• Double the input → about four times the work. This is quadratic 二次 growth.
• Comparing all pairs, filling an n × n grid: about n² steps.
• n² grows much faster than n as n gets large.

Comparing growth

• To compare algorithms, ask how the work grows as the input grows.
• For large n, an n algorithm beats an n² algorithm — often by a lot.
• Focus on the part of the code that runs the most (usually the innermost loop).
• The fastest-growing term dominates the total run time.