data-structures - O(L1 + L2) または O(max(L1, L2)) ですか?

Question

長さ L1 と L2 の 2 つのリストがあります。両方のリストを順番にトラバースしました。操作全体の時間計算量はどのくらいになるでしょうか?

O(L1 + L2) または O(max(L1, L2)) ですか?
2つの違いは何ですか？

Answer 1

両者に違いはありません。一般性を失うことなく、L1 = O(L2) と仮定します。そうでない場合は、L2 = O(L1) となり、シンボルを交換するだけです。

O(L1 + L2) = O(2*L2) = O(L2)。同様に、O(max(L1, L2)) = O(L2) です。したがって、どちらの場合も、複雑さは O(L2) です。