algorithm - 确定复杂性

Question

假设我已经给出了一个算法X , 它得到一个整数 n 作为输入.

现在考虑小于 x 的所有输入 n 的 X 需求(x是一个固定的任意自然数) O(n²) 步。但是对于每个输入 n > x它需要 n 个步骤。

问题X 的(最坏情况)运行时复杂度是多少？

答案: X 的(最坏情况)运行时复杂度为 O(n)。对于每个固定的 x，我们可以找到数字 n 使得 n>(x²) 和所有 n 的(最坏情况)运行时间为 n>(x²) 是在)。我不确定我的回答是否正确。

编辑:为了更好地理解 T(n, x) \in if n <= x then O(n^2)否则 O(n) .最坏情况下的运行时复杂度是多少？

Answer 1

具有成本函数(统一成本标准)的算法 X 的运行时复杂度 T(n, x)这是O(n^2)的成员什么时候n <= x , 否则是 O(n) 的成员，即:T(n, x) \in if n <= x then O(n^2) else O(n)是，如果我们修复 x \in Nat如你所说的任意数字，O(n) .

之所以如此，是因为一旦x是固定的，鉴于自然数没有界限，总有一个 n >= x^2 ，因此我们可以忽略 O(n^2)在处理算法的渐近时。

因此，R(n) = T(n, x) \in O(n) .

我觉得你的推理是合理的。