データ構造（リスト・辞書・タプル・集合）比較問題
リストと集合の検索性能の違いについて、最も正確な説明はどれですか？
A.リストの要素検索はO(1)で最も高速であり、集合の検索はO(n)で低速である
✗ 誤りです。逆です。リストの検索はO(n)の線形走査で、集合の検索はO(1)で高速です。
B.集合はハッシュテーブルに基づいており、要素検索がO(1)で高速。リストの検索はO(n)で線形走査が必要である← 正解
✓ 正解です。集合はハッシュテーブルで実装されており、要素検索がO(1)で高速。リストは順番に走査するためO(n)です。
C.リストと集合の検索性能に差はなく、サイズが同じであれば処理時間も同じである
✗ 誤りです。検索性能に大きな差があり、大量要素の検索は集合の方が効率的です。
D.集合は検索に特化した構造であるため全ての操作がO(1)で、リストはすべての操作がO(n)である
✗ 誤りです。すべての操作がO(1)ではなく、集合の追加・削除も平均的にはO(1)ですが、リストの追加・削除はO(n)です。