algorithm - 2 个变量输入的最坏情况大 (O) 复杂度

Question

我实现了一种算法，该算法将 R 行和 C 列的矩阵作为输入。我说算法的最坏情况时间复杂度是O(C√C * R^3) 或 O(C^1.5 * R^3)

现在有人问我，在最坏的情况下，它不能简单地表示为 O(R^3) 吗？我会说因为有 2 个输入(不是一个)，有时 C 可能很大，有时 R 可能很大，所以我们不能将它简化为简单的 O(R^3) 并且 C 和应考虑 R。

我的回答正确吗？如果不是，为什么？

Answer 1

是的，你是对的，在考虑时间复杂度时，你不能简单地忽略任何输入参数。

由于 C 和 R 在您的情况下都是未知的，我们需要考虑它们可以是任何值，因此除非指定，否则不能忽略任何值。

在您提到的情况下，时间复杂度必须指定为 O(C^1.5 * R^3)

现在请注意，在您的情况下，时间复杂度取决于输入参数变化的乘积，因此即使指定一个参数严格大于其他参数，我们也不能忽略它。而在增加复杂性的情况下，它可以被忽略。

举个例子。如果输入:R - 任何数字C - 任意数 >= R

在上面的例子中

O(R*C) = O(R*C) --> 我们不能忽略任何输入参数

O(R+C) = O(C) --> 正如我们所知，C 总是大于 R