題組內容

一、

⑵就您所知，有無現存的排序演算法，其最壞情況之時間複雜度可以達到上述之下限（lower bound）？若有，請舉一例說明之；若無，請說明理由。（10 分）

詳解 (共 1 筆)

詳解提供者：hchungw

合併排序和堆排序在最壞情況下的時間複雜度都達到了理論下限 O(nlog⁡n)。雖然快速排序的最壞情況時間複雜度為 O(n平方)，但通過適當的優化，快速排序在實際應用中依然非常高效。