アルゴリズム・プログラミング比較問題
バブルソートとクイックソートの最悪時間計算量の違いとして正しいものはどれか。
A.バブルソートの最悪計算量はO(n log n)、クイックソートの最悪計算量はO(n²)である
✗ バブルソートとクイックソートの最悪計算量が逆です。バブルソートがO(n²)、クイックソートの最悪もO(n²)です。
B.バブルソートの最悪計算量はO(n)、クイックソートの最悪計算量はO(n log n)である
✗ バブルソートの最悪計算量はO(n)ではなくO(n²)です。クイックソートの平均はO(n log n)ですが最悪はO(n²)です。
C.バブルソートの最悪計算量はO(n²)、クイックソートの最悪計算量もO(n²)であるが、平均ではクイックソートのほうが速い← 正解
✓ 正解です。両者の最悪計算量はともにO(n²)ですが、クイックソートは平均O(n log n)で実用上はるかに高速です。
D.バブルソートもクイックソートも最悪計算量はO(n log n)で同一である
✗ バブルソートの最悪計算量はO(n log n)ではなくO(n²)です。クイックソートの最悪もO(n²)となります。