阶乘代码处理大整数时运行时缩放异常的原因探究

我用Racket写了个计算阶乘的程序，测试不同n值下n!的运行时缩放情况，结果发现n增大时运行时的增幅差异特别大：

• n从10增至100，运行时约提升8倍
• n从1000增至10000，运行时提升380倍
• n从10000增至100000，运行时约提升42倍

我原本预期运行时会呈线性增长或遵循某种固定公式规律。

以下是相关代码：

#lang racket
(define (factorial-recursive n)
  (define (fact-iter n p)
    (if (= n 1)
        1
        (fact-iter (- n 1) (* p n))))
  (fact-iter n 1)
  )

(define (factorial-iterative n)
  (define (iter c p n)
    (if (> c n)
        1
        (iter (+ c 1) (* p c) n))
    )
  (iter 1 1 n)
 )
(define (time-iterative-factorial t )
  (define x (current-inexact-milliseconds))
  (factorial-iterative t)
  (- (current-inexact-milliseconds) x)
  )

(define (time-recursive-factorial t)
  (define x (current-inexact-milliseconds))
  (factorial-recursive t)
  (- (current-inexact-milliseconds) x)
  )

(time-recursive-factorial n)

不同n值的运行时缩放情况如下表：

内容的提问来源于stack exchange，提问作者Ege Çalışkan