0

在这里，我再次提出基本问题:(

如果我有下一个伪代码：

iterate over set (A)
    //some *O(1)* operations

iterate over set (B)
    //another *O(1)* operations

据我所知，时间是O(numberOfElementsInA + numberOfElementsInB)

但是，如果我知道B是A的子集并且numberOfElementsInA总是大于或等于 numberOfElementsInB ，我可以通过只写O(numberOfElementsInA)来简化时间吗？

4

1 回答 1

4

是的，你是对的。

这是因为numberOfElementsInA + numberOfElementsInB <= 2 * numberOfElementsInA, 并且根据大 O 符号的定义，它使得它O(numberOfElementsInA)(with c=2, and for each N)

编辑：确切地说，每个循环都是O(numberOfElementsInSet_i)- 因此每个循环都有常数c_i, N_i，因此T(loop_i) <= numberOfElementsInSet_i * c_i对于每个numberOfElementsInSet_i > N_i.
因此：

for each numberOfElementsInSet_1 > max{N1,N2}:
T(loop_1) + T(loop_2) <= numberOfElementsInSet_1 * c_1 + numberOfElementsInSet_2 * c_2
<= numberOfElementsInSet_1 * c_1 + numberOfElementsInSet_1 * c_2 //set1 is bigger
<= 2 * numberOfElementsInSet_1 * max{c_1,c_2}

现在我们有一个正式的证明，循环一起也O(numberOfElementsInSet_1)与N = max{N1,N2}和c = max{c_1,c_2} * 2

于 2012-10-22T23:19:47.173 回答