求Python程序的时间复杂度及列表长度计算精确公式

循环结构拆解 #

先逐层梳理calc(n)的执行逻辑：

• 最外层循环：初始i = n，每次将i取半向下取整，直到i ≤ 0停止。循环次数为m = ⌊log₂n⌋ + 1（比如n=1时循环1次，n=2_{3时循环2次，n=4}7时循环3次，以此类推）。
• 单次外层循环内的操作：
  1. 先执行1次li.append(1)。
  2. 进入j循环（从0到n-1，共n次迭代）：
     • 每次j循环先执行1次li.append(1)。
     • 再进入k循环（从j到n-1，共n-j次迭代），每次执行1次li.append(1)。

元素数量精确公式 #

计算单次外层循环中li新增的元素数量：

1. 先算j循环内的总操作数：
   $$\sum_{j=0}^{n-1} [1 + (n-j)] = \sum_{j=0}^{n-1}1 + \sum_{j=0}^{n-1}(n-j)$$
   • 第一部分是n个1相加，结果为n。
   • 第二部分等价于从1加到n，结果为$\frac{n(n+1)}{2}$。
   • 两者相加得：$n + \frac{n(n+1)}{2} = \frac{n^2 + 3n}{2}$。
2. 加上外层循环开头的1次append，单次外层循环新增元素数为：
   $$1 + \frac{n^2 + 3n}{2} = \frac{(n+1)(n+2)}{2}$$

结合外层循环次数m = ⌊log₂n⌋ + 1，最终len(li)的精确公式为：
$$len(li) = (\lfloor \log_2 n \rfloor + 1) \times \frac{(n+1)(n+2)}{2}$$

时间复杂度分析 #

由于Python的list.append()是**均摊O(1)**操作，程序的时间复杂度和li的元素数量增长趋势一致：

• $\frac{(n+1)(n+2)}{2}$属于$O(n^2)$量级。
• 外层循环次数m属于$O(\log n)$量级。
• 因此总时间复杂度为**$O(n^2 \log n)$**。

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