我又带着基本问题来了:(
如果我有下一个伪代码:
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) 来简化时间吗？
最佳答案
是的，你是对的。
这是因为numberOfElementsInA + numberOfElementsInB <= 2 * numberOfElementsInA , 来自definition of big O notation它使它成为O(numberOfElementsInA) (使用 c=2 ，以及每个 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
关于algorithm - 遍历相关集合的循环的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13021352/