單元7 測驗/排序 返回
關於快速排序法的複雜度，以下敘述何者正確？(A)平均效能為O(n log n) (B)最差效能為O(n log n) (C)最佳效能為O(n) (D)平均效能為O(n)
  • A. 平均效能為O(n log n)
    88.2% (15)
  • B. 最差效能為O(n log n)
    0% (0)
  • C. 最佳效能為O(n)
    0% (0)
  • D. 平均效能為O(n)
    11.8% (2)
解說:
答案是 (A) 平均效能為 O(n log n)。
解釋如下：
快速排序（QuickSort）是一種分治法排序演算法，它的性能在不同的情況下會有所不同。下面是各個選項的詳細解釋：
(A) 平均效能為 O(n log n)：這是正確的。快速排序的平均時間複雜度通常是 O(n log n)，這是因為在隨機或近似隨機的情況下，選擇pivot會把數據大致平衡地分割成兩個部分。這使得快速排序在大多數情況下可以達到 O(n log n) 的效能。
(B) 最差效能為 O(n log n)：這是錯誤的。快速排序的最差時間複雜度是 O(n^2)，這種情況通常發生在每次選擇的 pivot 都是數據中最小或最大元素（即每次分割都非常不平衡）。例如，對於已經排好序的數組，若每次選擇的 pivot 都是數組的最左或最右端元素，則時間複雜度變成 O(n^2)。
(C) 最佳效能為 O(n)：這是錯誤的。最佳情況下，快速排序的時間複雜度仍然是 O(n log n)，而不是 O(n)。
(D) 平均效能為 O(n)：這是錯誤的。快速排序的平均時間複雜度通常是 O(n log n)，而不是 O(n)。
總結來說，快速排序的 平均效能 是 O(n log n)，所以正確答案是 (A)。
答對率 : 88.2 %
利用氣泡排序法將數值由小到大排序，下列那一堆原始數值在執行此排序法的過程中，其實際之數值互換次數最少？ 
  • A. 10,15,7,13,11
    0% (0)
  • B. 20,18,9,25,16
    11.8% (2)
  • C. 10,12,15,20,23
    70.6% (12)
  • D. 25,20,17,16,5
    17.6% (3)
解說:
答案是 (C) 10, 12, 15, 20, 23。
解釋：
氣泡排序法（Bubble Sort）是通過反覆比較並交換相鄰的元素，將較大的元素“氣泡”到數列的末尾。若要將數列由大到小排序，氣泡排序會比較相鄰的元素，若左邊的元素比右邊的元素小，則進行交換，直到整個數列排序完成。
在這個過程中，互換次數的多少取決於原始數列的“逆序數”或“排序程度”。逆序數是指在數列中，較大的數值出現在較小的數值前面的次數。氣泡排序需要進行交換的次數與數列的逆序數成正比——逆序數越多，交換次數越多。
分析每個選項的逆序數：
(A) 10, 15, 7, 13, 11
初始數列的逆序數： (15, 7), (15, 13), (15, 11), (10, 7), (10, 13), (10, 11) — 共 6 組逆序。
需要進行至少 6 次交換。
(B) 20, 18, 9, 25, 16
初始數列的逆序數： (20, 18), (20, 9), (20, 16), (18, 9), (18, 16), (9, 16) — 共 6 組逆序。
需要進行至少 6 次交換。
(C) 10, 12, 15, 20, 23
初始數列的逆序數：這是一個已經是升序排列的數列，因此逆序數為 0。
因為沒有逆序，氣泡排序不需要進行任何交換。
(D) 25, 20, 17, 16, 5
初始數列的逆序數： (25, 20), (25, 17), (25, 16), (25, 5), (20, 17), (20, 16), (20, 5), (17, 16), (17, 5), (16, 5) — 共 10 組逆序。
需要進行至少 10 次交換。
結論：
選項 (C) 是一個已經排好序的數列，因此不需要進行任何交換，互換次數是最少的。
其他選項的數列需要進行一定次數的交換。
所以，答案是 (C) 10, 12, 15, 20, 23。
答對率 : 70.6 %
使用比較與交換（Comparisons and Interchanges）的排序方法中，最佳的時間複雜度為： (A)O(n log n) (B)O(n^2) (C)O(n^3) (D)O(n^4) 
  • A. O(n log n)
    70.6% (12)
  • B. O(n²)
    11.8% (2)
  • C. O(n³)
    5.9% (1)
  • D. O(n⁴)
    5.9% (1)
  • 未填寫
    5.9% (1)
解說:
在排序演算法中，比較與交換（Comparisons and Interchanges） 這一術語通常是指基於比較的排序方法，比如快速排序（QuickSort）、合併排序（MergeSort）等。這些排序算法在排序過程中會反覆比較元素，並根據比較結果進行交換或調整。
其中，最理想的時間複雜度是 O(n log n)，這是很多高效排序算法的最佳時間複雜度。這些排序算法的基本思想是：
(1)快速排序（QuickSort）：在平均情況下，它的時間複雜度是 O(n log n)。最差情況下是 O(n²)，但可以通過選擇適當的pivot來減少最差情況的機會。
(2)合併排序（MergeSort）：歸併排序的時間複雜度為 O(n log n)，無論是最壞情況、平均情況還是最佳情況。
這些算法的時間複雜度 O(n log n) 是基於分治法或堆積結構來提高效率，並且已經是基於比較的排序算法中最佳的時間複雜度。
其他選項解釋：
(B) O(n²)：這是像氣泡排序、插入排序和選擇排序等算法的時間複雜度。這些排序算法通常適用於小規模數據，或者當數據已經接近排序時。
(C) O(n³) 和 (D) O(n⁴)：這些時間複雜度對於排序算法來說非常低效，通常不會出現在基於比較的排序算法中，因為它們需要的操作量過大。
結論：
最佳的時間複雜度是 O(n log n)，這對應於高效的比較排序算法，如快速排序、歸併排序和堆排序。因此，正確答案是 (A) O(n log n)。
答對率 : 70.6 %
下列何者對於排序方法的敘述錯誤？
  • A. 合併排序法在最差的情況下，時間複雜度為O（n log n）
    5.9% (1)
  • B. 快速排序法在最差的情況下，時間複雜度為O（n log n）
    52.9% (9)
  • C. 氣泡排序法在最差的情況下，時間複雜度為O（n²）
    23.5% (4)
  • D. 堆積排序法在最差的情況下，時間複雜度為O（n log n）
    11.8% (2)
  • 未填寫
    5.9% (1)
解說:
答案是 (B) 快速排序法在最差的情況下，時間複雜度為 O(n log n)。
解釋：
(A) 合併排序法在最差的情況下，時間複雜度為 O(n log n)：
正確。合併排序（MergeSort）無論是最佳情況、最差情況，還是平均情況下的時間複雜度都是 O(n log n)。它是一種穩定的排序算法，且具有良好的時間複雜度。
(B) 快速排序法在最差的情況下，時間複雜度為 O(n log n)：
錯誤。快速排序（QuickSort）在最差情況下的時間複雜度是 O(n²)，而不是 O(n log n)。最差情況通常發生在每次選擇的 pivot 都是數列中的最小或最大元素，這會導致每次只分割一個元素，從而退化成氣泡排序的效果，時間複雜度為 O(n²)。
不過，在大多數情況下，快速排序的平均時間複雜度是 O(n log n)，並且可以通過選擇更好的pivot 來減少最差情況的發生。
(C) 氣泡排序法在最差的情況下，時間複雜度為 O(n²)：
正確。氣泡排序（BubbleSort）在最差情況下的時間複雜度是 O(n²)，通常發生在數列是逆序時。氣泡排序的最差情況需要進行大量的比較和交換，因此其時間複雜度為 O(n²)。
(D) 堆積排序法在最差的情況下，時間複雜度為 O(n log n)：
正確。堆積排序（HeapSort）在最差情況下的時間複雜度是 O(n log n)，無論是最佳、最差還是平均情況。堆積排序是一種基於堆資料結構的排序方法，時間複雜度是 O(n log n)。
結論：
選項 (B) 錯誤，因為快速排序在最差情況下的時間複雜度是 O(n²)，而不是 O(n log n)。
答對率 : 52.9 %
利用插入排序法對n 筆資料排序，在平均情況下（average-case）所需的執行時間複雜度（time complexity）為何？選最恰當的： (A) O (n) (B) O (n log n) (C) O (n²) (D) O (n²log n)
  • A. O (n)
    17.6% (3)
  • B. O (n log n)
    5.9% (1)
  • C. O (n²)
    70.6% (12)
  • D. O (n²log n)
    0% (0)
  • 未填寫
    5.9% (1)
解說:
答案是 (C) O(n²)。
解釋：
插入排序法（Insertion Sort） 是一種簡單的排序算法，它的基本思想是將待排序的元素逐一插入到已排序的部分，這樣每插入一個元素就能保持已排序部分的有序性。具體來說，它會將當前元素與已排序部分的元素進行比較，並把當前元素插入到適當的位置。
平均情況下的時間複雜度：
在 平均情況 下，插入排序的每一個元素需要進行大約 n/2 次比較和交換，這是因為每插入一個元素，平均需要和已排序的元素進行一半的比較。
因此，對於 n 個元素，平均的時間複雜度是 O(n²)。
 
其他選項解釋：
(A) O(n)：這是最佳情況下的時間複雜度，當數列已經是有序時，插入排序的時間複雜度為 O(n)。
(B) O(n log n)：這是像合併排序、快速排序這些高效排序算法的平均情況下的時間複雜度，但插入排序的時間複雜度並不是這樣。
(D) O(n² log n)：這種複雜度通常不會出現在插入排序這樣的算法中，因為插入排序的基本操作並不涉及類似於 log n 的因素。
結論：
因此，正確的答案是 (C) O(n²)，這是插入排序在 平均情況下 的時間複雜度。
答對率 : 70.6 %
下載答題分析