我可以理解算法中的运行时间复杂度。但是当我们知道算法运行时间复杂度为 O(n) 时，这有点令人困惑。
我们可以看出 f(n)< g(n)..
g(n)到底是什么..？
对不起菜鸟问题..
谢谢。
问问题
128 次
2 回答
1
让f(x)和g(x)是在实数的某个子集上定义的两个函数。一个写
f(x) = O(g(x)) as x -> infinity
当且仅当存在一个正实数M和一个实数x0使得
|f(x)| <= M |g(x)| for all x > x0
一般而言，f(x)是算法在输入规模上的实际成本（例如执行步骤数）x，而比用于表征 的复杂性行为g(x)要简单得多。f(x)f(x)
于 2012-11-20T02:27:33.053 回答
0
我同意 f(x) 和 g(x) 只是一对函数的评论。f(x) = O(g(x)) 告诉我们它们以特定的方式相关。
这通常使用的方式是使 f(x) 成为一些复杂的、难以表征的函数。g(x) 是一个更简单的函数。知道 f(x) = O(g(x)) 让我们感觉随着 x 的增加， f(x) 的界限。
在计算机科学中的应用是使 f(x) 作为输入大小 x 的函数来衡量程序行为。例如，f(x) 可能是对 x 元素数组进行排序时的最大比较次数，或者是某些算法中使用的内存字数。f(x) 通常会非常混乱。
我们可以通过找到一个好的、干净的函数 g(x) 来使事情变得更简单，这样我们就可以证明 f(x) = O(g(x))。
例如，对于小于 30 的输入，某些算法实际上可能在其输入中每个元素采用 35 次操作或 10 次操作中的较大者，或者对于所有较大的输入，每个元素采用 1000 次操作中的较大者。
如果我们只注意到 f(x) = O(x)，那么比较算法会更简单，也更容易。
请注意，这与说 f(x) < g(x) 不同。在我的示例中，对于较大的 x，f(x) 是 g(x) 的一千倍。它只是意味着 g(x) 捕获了 f(x) 在 x 变大时的行为方式。
于 2012-11-20T02:25:12.927 回答