一个例子是两个不在彼此内的 for 循环。它仍然等于0（n）吗？还有为什么我要问一个 Stringbuilder 构造函数在字符串中发送的时间复杂度。
问问题
229 次
4 回答
0
StringBuilder内部arraycopy(Object, int, Object, int, int)在构造函数调用和追加方法调用时使用本机，我认为这比2 for循环更有效。
于 2012-10-18T03:47:58.470 回答
0
O(n) + O(n) = O(n + n) = O(n)。事实上，对于任何（有限）常数 k，O(k * n) = O(n)。
但是对于实际的编程问题，O(n) 的考虑通常远不如所涉及的系数重要。具有大系数的 O(n) 算法在实践中可能比具有小系数的 O(2 n ) 算法差得多。
最好发布您的代码替代方案，以及对问题规模的估计，并询问哪个更有效。
于 2012-10-18T03:48:14.083 回答
0
问题不清楚。
但如果你的意思是，两个 O(n) 代码一个接一个，那么它仍然是 O(n)。
Lim (2*n/n) = 2 (constant).
n->INF
因此 O(N) 既是上限又是下限，这意味着theta(N) => O(n)
于 2012-10-18T03:51:19.687 回答
0
时间复杂度问题：
说一个算法是 O(n) 意味着该算法最多需要 n*k 步，其中 n 是输入大小， k 是任意常数。因此，无论算法采取 n 步、2n 步、(1/2)n 步、100n 步还是 1000000n 步都没有关系，它仍然是 O(n)。
因此，如果你有两个 O(n) 算法，它们每个都有一些常数 k，它给出了它们相对于 n 采取的步数：比如 k1*n 和 k2*n。如果您同时运行这两种算法，它将采取的步骤数是：
k1*n + k2*n
这与以下内容相同：
(k1 + k2)*n
...因为 n 是一个公因数。并且由于 k1 和 k2 都不会随 n 增长（因为它们是常数），因此它们的和k1 + k2 不会随 n 增长。这意味着 k1 + k2 仍然是一个常数，因此运行时仍然是 n 的常数倍。
字符串生成器问题：
我不知道，但如果我是你，我会尝试以增加字符串长度来运行构造函数，看看每次需要多长时间。您可以通过当字符串变大时构造函数减速的速度来判断复杂性。
于 2012-10-18T04:26:35.470 回答