时间戳

首页 > 解决方案 > 2 个变量输入的最坏情况大 (O) 复杂度

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

问题描述

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

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

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

标签： algorithmbig-o

解决方案

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

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

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

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

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

在上述情况下

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

O(R+C) = O(C)--> 我们知道 C 总是大于 R

推荐阅读