big-o - 概率函数可以用作计算代码复杂度的一部分吗

Question

如何将概率函数作为代码复杂性分析的一部分。

if (cond1(l,n)) {
   for (int r=l;r<n;r++)
      for (int m=r;m<n;m++)
          for (int k=m;k<n;k++)
               //calculation
} else
    // calculation

此代码的典型复杂度分析将产生复杂度为 O(N^3)。

假设 cond1(l,n) 显着产生错误，因此在假设计算中跳过内部 for 循环。

我想尽可能准确地计算代码的复杂度，因为我想比较一系列类似算法的复杂度。

例如，我想用减少内部循环调用的不同算法集替换 cond1(l,n)。

如何尽可能准确地计算算法的复杂度。

我试图分析的代码的一个现实场景是 [link] Analyzing an index recursive function

Answer 1

复杂性分析不是这里工作的正确工具：它旨在粗略了解随着问题规模的扩大会发生什么。如果您正在寻找运行时的精确分析，您希望改为对代码进行基准测试或分析。