通过复合函数计算的算法复杂度

Question

有没有用复合函数计算复杂度的算法？ 假设我们有 f 属于 O(n^2)，g 属于 O(n)。是否存在复杂度为 f(g(n)) 的算法， 是 O(n^2).

Answer 1

我在现实生活中从未遇到过这种情况，但你可以想象这样的算法。例如，一种在运行时分析另一个算法的算法。例如，你可以有不同的基于比较的排序算法，以及一个算法分析器，它存储所有完成的比较，测量它们花费的时间，对它们进行排序，对它们进行一些统计等等。如果第二个算法具有复杂性 f(n)在它作为条目获得的比较次数中，并且排序算法具有 g(n) 复杂度，然后 运行 对大小为 n 的输入的排序算法的分析具有 n 的总复杂度=13=].

总之这有点诡计，因为显然 n 在 f(n) 和 g(n) 中不是一回事。基本上 运行 一个算法 algo2 在 algo1 的输出上，其大小与其复杂性大致相同。