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)から、 （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

于 2012-10-22T23:19:47.173 に答える