计算法的复杂性混乱

StackOverflow https://stackoverflow.com/questions/2233938

题

我有以下代码段：

sum = 0;
for (i = 0; i < n; i++)
    for (j = 0; j < i; j++)
        sum++;

复杂性会 O(n^2), 但是如果我想要挖多一点的内部循环的复杂性，然后它会是 (n (n-1))/2 或 (n-1)!?

有帮助吗？

解决方案

是的,O(n^2)，但实际上0+1+...+n-1=n(n-1)/2=O(n^2)，肯定不是(n-1)!

其他提示

time = n*(n-1)/2
     = (n*n - n)/2

由于大O符号是一个上限，较小的顺序期(n)和不断的因素(1/2)都是删除(因为它们不显着的表示该上限的时间)，以产生很大的-O符号， O(n*n) 更好地称为 O(n^2).

你可能有个算法运行在时间

22222222222222 + 4444444444444*n + 9999999999999999999999999*n^2 steps

和它仍然是O(n^2).

它是一个开放的问题找到一个更好的描述的算法运行时间比O.

常量是无关紧要尽很大的-O符号表示关注。

你有什么计算出的 (n(n-1)/2) 是的确切数量的迭代码。当被问及对时间的复杂性条款，如果大O，你得到一个估计，它只是个足够大，以表达所需的时间。

换句话说，你需要找到 THE SMALLEST power 的 n 例如，对于一些 k (k>0), k * n^power 将大于确切数量的迭代。在你的情况， k 恰好是 1 和 power 恰好是 2.然后 O(n^power) 是你的时间复杂性。

第一， (n-1)! 装置 (n-1)(n-2)...(2)(1).这显然不是，你想要什么在这里。

如果你计算的实际数量的迭代它的 0 + 1 + 2 + ... + (n-2) + (n-1).注意有 n 条款的总和，而且我们可以对他们关在一个方式，这样的平均值，每一对 (n-1)/2.(对最高和最低的，高居第二和第二低的，等等)。 如果 n 是奇怪，你会有一个留下，不能进行配对，但是便利，其价值也是 (n-1)/2.因此你有 n 条款以及平均的所有条款是 (n-1)/2, ，因此总是 n(n-1)/2.

现在，大O符号不论究竟有多少次迭代，我们有...我们只是想知道限时 n 是非常大的。注意，我们的迭代的次数可以写作 (1/2)n^2 - (1/2)n.对于非常大 n, ， n^2 期是方式，方法比 n 术语，所以我们放下 n 术语。刚刚离开我们 (1/2)n^2, 但另一条规则的大O符号是我们不关心的恒的因素，因此，我们只是写的，这是O(n^2).

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top