三层嵌套循环函数my_func的运行时间计算与时间复杂度问题咨询

1. 时间复杂度结论验证 #

你的结论是正确的。
我们可以精确计算最内层some_other_func()的执行次数：三层循环的约束是n>i>j>k≥1，所有符合条件的三元组数量等于从n-1个元素中选3个的组合数，即$C_{n-1}^3 = \frac{(n-1)(n-2)(n-3)}{6}$，这个表达式的最高次项是$\frac{1}{6}n^3$。你通过每层循环的最大执行次数估算得到O(n³)的结果，完全符合大O记号的上界定义，推导逻辑成立。

2. 渐近运行时间定义及本算法结果 #

• 渐近运行时间定义：用来描述输入规模n趋向于无穷大时，算法运行时间的增长趋势的度量标准。计算时会忽略常数系数、低阶项这些对增长趋势影响极小的部分，只保留最高阶的增长量级，能够快速对比不同算法的效率差异，不需要关注具体硬件、编程语言带来的常数级性能波动。
• 本算法的渐近运行时间：紧渐近界为$\Theta(n^{3)$，如果仅表示上界则为$O(n}3)$，二者在工程场景中通常都可以用来描述该算法的时间复杂度。

3. 公式含义解释 #

你给出的是大O记号的严格数学定义，公式如下：

具体含义：对于两个定义域为正整数的函数f(n)和g(n)，如果存在正的常数c和正整数$n_0$，使得所有满足$n \geq n_0$的n，都有不等式$0 \leq f(n) \leq c \cdot g(n)$成立，那么我们就可以记作$f(n) = O(g(n))$。
通俗来说就是：当输入规模n足够大（超过阈值$n_0$）之后，算法的实际运行时间f(n)的增长速度永远不会超过g(n)的某个常数倍，我们就可以用更简洁的g(n)来代表该算法的时间增长上限。

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