确定复杂性

Determine the complexity

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

作为输入

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

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

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

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

根据定义,对于 Big-Oh(或任何复杂性界限)而言,重要的是 n 的所有值在某个固定界限之上的行为。您的算法最终在 n 中是线性的,因此运行时间受 O(n).

约束

请注意,如果您的算法接受 n 的输入,这实际上意味着接受 n 在某些数字系统中的表示。在典型的计算机上,这将是 2 位(二进制)表示。 base-k(k-ary)表示将采用 log_k(n) 数字,四舍五入。所以如果你在二进制系统中,数字是 9,表示是 1001,它占用 4 位(log base 2 of 9 大于 3 但小于 2,所以四位)。

鉴于此,您的输入大小实际上不是 n,而是 log_2(n)(假设二进制),如果您的算法需要时间 n,则运行时间 w.r.t。输入大小实际上是指数级的(因为 n = 2^(log_2 n))。

这是一个小问题,但可能会让您以不同的方式思考算法。如果不是取一个数字而是取一个包含 n 元素的列表,区别就消失了。

算法 X 的运行时复杂度与成本函数(统一成本标准)T(n, x)n <= x 时它是 O(n^2) 的成员,否则是 [=13 的成员=],即: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).

我觉得你的推理很有道理。