如何依据输入规模与耗时数据估算程序平均情况时间复杂度？

Great question! Let's walk through how to interpret your data, what conclusions you can draw, and where the limits of this approach lie.

First: What Your Data Already Reveals #

Let's start by breaking down your input sizes (n) and corresponding runtimes (t) to spot clear trends:

• n=12: 0.1155s
• n=13: 0.1237s
• n=14: 0.2076s
• n=15: 0.5189s
• n=16: 1.642s
• n=17: 7.625s

The most useful metric here is the ratio of runtimes between consecutive n values—this tells us how much slower the program gets as input size grows:

• 12→13: ~1.07x slower
• 13→14: ~1.68x slower
• 14→15: ~2.5x slower
• 15→16: ~3.16x slower
• 16→17: ~4.64x slower

Notice that this ratio isn't constant—it's accelerating as n increases. That immediately rules out polynomial time complexities like O(n), O(n²), or O(n³): those would have ratios that stay roughly steady (for O(n)) or grow slowly (for O(n²)). Your runtime is growing way faster than any polynomial can account for.

Likely Candidates: Exponential or Factorial Growth? #

The two most common super-polynomial complexities fit your data's trend, but we can narrow it down:

1. Exponential (O(kⁿ) for some constant k) #

For pure exponential growth, every time n increases by 1, runtime multiplies by a fixed k (e.g., k=2 for O(2ⁿ)). But your ratios are increasing, not staying constant. This doesn't perfectly match—unless low-order terms or program overhead (like input parsing, memory setup) are masking the true exponential trend at small n.

2. Factorial (O(n!)) #

Factorial growth is even faster than exponential: (n+1)! = (n+1) * n!, so the runtime ratio should approach n+1 as n gets large. While your ratios aren't hitting n+1 yet (e.g., n=17 would imply a 17x jump, but you only see 4.64x), this makes sense for small n: fixed program overhead takes up a huge chunk of runtime when n is small. As n grows, that overhead becomes negligible, and the ratio will start approaching n+1.

Your data's accelerating ratio aligns much better with factorial growth than pure exponential.

How to Confirm Your Guess #

To get a more definitive answer, try these steps:

• Test larger input sizes: Run the program for n=18 and n=19. If the runtime ratio jumps to ~18x and ~19x, that's a dead giveaway for O(n!). If it stabilizes around a fixed k (like 5x), then it's O(5ⁿ) or similar.
• Logarithmic fitting: Take the logarithm of your runtime values (e.g., log₂(t)). For:
  • Exponential growth (O(kⁿ)), log(t) will be linear with n (since log(kⁿ) = n*log(k)).
  • Factorial growth (O(n!)), use Stirling's approximation: log(n!) ≈ n*log(n), so log(t) should be linear with n*log(n).
    Plot these values and see which gives a straighter line—this will tell you which complexity fits best.

The Catch: You Can't Be 100% Certain (Yet) #

Small input sizes always come with noise: constant factors, low-order terms, and program overhead can skew your data. Your current data gives you a strong, evidence-based guess, but to confirm the exact asymptotic complexity, you need larger n where the core algorithm's behavior dominates the runtime.

内容的提问来源于stack exchange，提问作者Georgi Spasov