コンピュータのすべての可能なペアのリスト効率

Question

私は2つの数字のセットを持っていると私はそれの中のすべてのペアの値を構築したいと思います。例：

A = {1, 2} 
B = {3, 4} 
Out = {(1,3), (1,4), (2,3), (2,4)} 

私のセットには、O（1）の検索時間があります。私の出力をO（| A | + | B |）で計算することも可能です。セットが同じサイズではないのに、私はこの解決策を見つけられません。 O（n^2）]である。あなたは私に与えられた複雑さでこれをどのように計算することができるかを私に示唆してくれますか？

Answer 1

いいえ、あなたは2つ以上のループではできません。このように考える。 Aのすべての要素に対して、B要素を出力する必要があります。だからあなたのランニングタイムは常にA * Bの倍数になります。

さんがAだからあなたが最初のセットと出力の6つの要素を持っている3つの要素

A = {1, 2, 3} 
B = {3, 4} 
Out = {(1,3), (1,4), (2,3), (2,4), {3,3}, {3,4}} 

を持っているため上記のあなたの例を変更してみましょう| A | = 3および| B | = 2.あなたの出力は| A | + | B |したがって、あなたは当初の仮定は真ではありません。

最適な最適化は、要素ごとにO（1）時間にセットの要素を列挙できることを確認することです。