2 个变量输入的最坏情况大 (O) 复杂度
Worst case Big (O) complexity for 2 variable input
我实现了一种算法，该算法将 R 行和 C 列的矩阵作为输入。
我说算法的最坏情况时间复杂度是
O(C√C * R^3) 或 O(C^1.5 * R^3)
现在有人问我，在最坏的情况下，它不能简单地表示为 O(R^3) 吗？
我会说，因为有 2 个输入（不是一个），有时 C 可能很大，有时 R 可能很大，所以我们不能将其简化为 O(R^3) 并且 C 和 R 都应该考虑在内。
我的回答正确吗？
如果不是，为什么？
是的，你是对的，在考虑时间复杂度的时候不能简单地忽略任何一个输入参数。
由于您这两种情况下的 C 和 R 都是未知的，我们需要考虑它们可以是任何值，因此除非指定，否则不能忽略任何值。
在您提到的情况下，时间复杂度必须指定为 O(C^1.5 * R^3)
现在请注意，在您的情况下，时间复杂度取决于输入参数变化的乘积，因此即使指定一个参数严格大于其他参数，我们也不能忽略它。而在增加复杂性的情况下，它可以被忽略。
举个例子。
如果输入：
R - 任何数字
C - 任意数字 >= R
在上述情况下
O(R*C) = O(R*C) --> 我们不能忽略任何输入参数
O(R+C) = O(C) --> 正如我们所知，C 总是大于 R
你说得对，在你的 Big O 表达式中应该考虑 C 和 R。
大O分析在输入大小可能变化的情况下很有用，这里输入的大小需要两个参数来描述，因为你说“有时C可以很大，有时R可以很大” .
如果 C 是 O(1)，那么消除 C 的唯一方法是，在这种情况下，您的函数将增长为 O(R^3)，或者如果 C 是 R 的函数，例如如果 C = O(R)，您的函数将增长为 O(R^4.5)。
我实现了一种算法，该算法将 R 行和 C 列的矩阵作为输入。
我说算法的最坏情况时间复杂度是
O(C√C * R^3) 或 O(C^1.5 * R^3)
现在有人问我，在最坏的情况下，它不能简单地表示为 O(R^3) 吗？
我会说，因为有 2 个输入（不是一个），有时 C 可能很大，有时 R 可能很大，所以我们不能将其简化为 O(R^3) 并且 C 和 R 都应该考虑在内。
我的回答正确吗？ 如果不是，为什么？
是的，你是对的，在考虑时间复杂度的时候不能简单地忽略任何一个输入参数。
由于您这两种情况下的 C 和 R 都是未知的，我们需要考虑它们可以是任何值，因此除非指定，否则不能忽略任何值。
在您提到的情况下，时间复杂度必须指定为 O(C^1.5 * R^3)
现在请注意，在您的情况下，时间复杂度取决于输入参数变化的乘积，因此即使指定一个参数严格大于其他参数，我们也不能忽略它。而在增加复杂性的情况下，它可以被忽略。
举个例子。 如果输入： R - 任何数字 C - 任意数字 >= R
在上述情况下
O(R*C) = O(R*C) --> 我们不能忽略任何输入参数
O(R+C) = O(C) --> 正如我们所知，C 总是大于 R
你说得对，在你的 Big O 表达式中应该考虑 C 和 R。
大O分析在输入大小可能变化的情况下很有用，这里输入的大小需要两个参数来描述，因为你说“有时C可以很大，有时R可以很大” .
如果 C 是 O(1)，那么消除 C 的唯一方法是，在这种情况下，您的函数将增长为 O(R^3)，或者如果 C 是 R 的函数，例如如果 C = O(R)，您的函数将增长为 O(R^4.5)。