如何将概率函数作为代码复杂性分析的一部分?
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)明显产生false，因此在假设计算中跳过内部for循环。
我希望尽可能准确地计算代码的复杂度，因为我想比较一系列相似算法的复杂度。
例如，我想用一组不同的算法来替换cond1(l,n)，以减少内部循环调用。
我怎样才能尽可能准确地计算出算法的复杂度。
我试图分析的代码的一个现实场景是在[链接]分析一个指数递归函数
复杂性分析不是适合这里的工作的工具:它的目的是给出一个粗略的概念，随着问题规模的扩大会发生什么。如果您正在寻找对运行时的精确分析，那么您需要对代码进行基准测试或概要分析。