如何确定给定OCaml函数的时间复杂度？我的O(log(n)²)推导是否正确？

你的结论是正确的，该函数的时间复杂度为O((log n)²)，以下是详细推导过程：

1. 拆解函数逻辑 #

先明确目标函数的核心逻辑：

let biggest_factorial_below n =
  let i = ref 1 in
  while (fact !i < n) do
    i := !i + 1;
  done;
  !i

它通过循环调用fact函数，找到最大的整数i使得i! < n。我们需要分两步分析：循环执行的次数，以及每次循环的时间成本。

2. 确定循环执行的次数 #

要找到满足i! < n的最大i，可以用斯特林近似估算i的量级：
斯特林公式简化为：ln(i!) ≈ i ln i - i（忽略低阶小项）。当i! < n时，取自然对数得：

i ln i - i ≈ ln n

对于大n，主导项是i ln i ≈ ln n，解这个方程可得i的量级为Θ(log n / log log n)——这个增长速度比log n稍慢，但仍然属于O(log n)的范畴。

3. 计算单次循环的时间成本 #

递归阶乘函数fact k的时间复杂度是O(k)：

let rec fact n =
  match n with
  | 0 -> 1
  | n -> n * fact (n - 1)

它需要执行k次递归调用和乘法操作，时间与输入k线性相关。

4. 总时间复杂度求和 #

循环会从i=1执行到最终的i，总时间是各次循环的时间之和：

O(1) + O(2) + ... + O(i)

这是等差数列求和，结果为O(i²)（因为1+2+...+i = i(i+1)/2，渐近等价于i²）。

5. 结合得到整体复杂度 #

由于i是O(log n)，代入后总时间复杂度为O((log n)²)。即使更精确的i是Θ(log n / log log n)，i²仍然是O((log n)²)（因为(log log n)²增长极慢，不会改变上界）。

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