教甄◆電腦科專業題庫下載題庫

原本題目:

下列關於「排序 n 個數字」的敘述何者不正確？ (A) 任何只使用比較 (comparison) 來排序的演算法都需要 Ω(n log n) 的時間。 (B) 由於整數排序法 (integer sort) 的時間複雜度與數字的範圍有關，若已知此 n 個數字都是介於 1 到 n7 之間的正整數，則可在 O(n7) 的時間複雜度完成排序，但無法在 O(n) 的時間複雜度完成。 (C) 堆疊排序法 (heap sort) 與合併排序法 (merge sort) 的時間複雜度皆為 O(n log n)。 (D) 快速排序法 (quick sort) 的時間複雜度為 O(n2)。

修改成為

下列關於「排序 n 個數字」的敘述何者不正確？ (A) 任何只使用比較 (comparison) 來排序的演算法都需要 Ω(n log n) 的時間。 (B) 由於整數排序法 (integer sort) ...

原本題目:

下列關於「排序 n 個數字」的敘述何者不正確？ (A) 任何只使用比較 (comparison) 來排序的演算法都需要 Ω(n log n) 的時間。 (B) 由於整數排序法 (integer sort) 的時間複雜度與數字的範圍有關，若已知此 n 個數字都是介於 1 到 n7 之間的正整數，則可在 O(n7) 的時間複雜度完成排序，但無法在 O(n) 的時間複雜度完成。 (C) 堆疊排序法 (heap sort) 與合併排序法 (merge sort) 的時間複雜度皆為 O(n log n)。 (D) 快速排序法 (quick sort) 的時間複雜度為 O(n2)。

修改成為

下列關於「排序 n 個數字」的敘述何者不正確？ (A) 任何只使用比較 (comparison) 來排序的演算法都需要 Ω(n log n) 的時間。 (B) 由於整數排序法 (integer sort) 的時間複雜度與數字的範圍有關，若已知此 n 個數字都是介於 1 到 n⁷ 之間的正整數，則可在 O(n⁷) 的時間複雜度完成排序，但無法在 O(n) 的時間複雜度完成。 (C) 堆疊排序法 (heap sort) 與合併排序法 (merge sort) 的時間複雜度皆為 O(n log n)。 (D) 快速排序法 (quick sort) 的時間複雜度為 O(n²)。