在DAY21天以後我們介紹了演算法的三種排序，以及提到了時間複雜度的意義。而在"三種sorting實作"的三部曲中，我們先從程式介紹的部分下手，讓大家對實際混合比較的演算法執行較有概念，且在途中講到了CPU頻率的使用方法，而今天，我們就要以上述兩者為基礎來為各位演示"效能分析"的過程與圖表比較、說明。
首先我們以10、100、1000、10000、100000帶入n值(陣列大小)，因為若是"僅取一固定值進行比較"的結果相較於"取較多次樣本"的結果比起來較不準確，故我們取較多次進行更全面的比對。並計算三種sorting分別的print(有輸出結果)和去除掉print的(沒有輸出結果)的執行時間如下表格所示，時間單位為秒:
我們由有無print的比較可以看出有時若是我們僅是將執行時間設為全程式的執行時間，以本題為例，那會因為print的輸出時間過長而看不出彼此的差異，故我們將print屏蔽掉後更能看出time complexity在不同情況下具體的影響與差異。
由第二個比較圖可以看出insertion sort的時間遠大於quick和merge sort，因其時間複雜度為(n^2)
而我們又單獨拉出quick sort與merge sort進行比較，可以看出merge sort略慢於quick sort，但兩者仍十分接近。因為他們兩個的時間複雜度均是nlogn，電腦cpu的速度也會影響時間複雜度的運行。
最後，我們來探討三者更深的比對:
insertionSort的最好情況是O(1)，而平均情況是O(n^2)；quickSort的最好情況是O(nlogn)而最慘情況是O(n^2)，取決於樞紐選擇的大寫是否愈接近中位數；mergeSort的固定時間複雜度是O(nlogn)，但會用到比較多的memory資源。
而從三個圖表(分別是有輸出結果&沒有輸出結果&單獨列出沒有輸出結果的quick和mergeSort)，從第三張圖可以看出quickSort快於mergeSort，也許在時間複雜度上看起來並不是如此(理論上兩者皆為nlogn)，但因為在實際執行上我們用迴圈方式，quickSort和mergeSort分別花費N和2N-1(分割前加上分割後)的時間在遞迴上，mergeSort多花了許多時間在記憶體上，因此時間會多於quickSort，但就其仍有不會因為數列順序影響的良好穩定特性。
因此我們也會視情況使用不同特性的演算法，像是若是記憶體空間充足便可以採用mergeSort，具有最好的排序穩定性(不受到任何輸入的陣列大小與順序影響)、而若是空間不足的情況也可採用quick sort達到結果。
經過三十天的挑戰，相信你/妳對於C++這個程式語言有著基本的架構與語法認識，也開始能夠撰寫自己的程式碼，而最後的十天我們也帶到了一些演算法的概念，若是有興趣也能夠再自己查閱更多的資料與線上影片、課程，畢竟資訊領域日新月異，若要一直進步就需要不斷的充實與練習。而我自己也仍在這廣闊的領域邁步與吸收、學習。希望這三十天的小小分享能為大家開拓一些程式初心者的挑戰之旅與些許的解惑，謝謝大家閱讀至此，「C++的30天挑戰之旅」下台一鞠躬 ~٩(๑•̀ω•́๑)۶
iThome鐵人賽
看影片追技術