算法的時間復雜度實驗報告_第1頁
算法的時間復雜度實驗報告_第2頁
算法的時間復雜度實驗報告_第3頁
全文預覽已結束

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、實驗一算法的時間復雜度1、 實驗目的與要求熟悉C/C+語言的集成開發環境；通過本實驗加深對算法分析基礎知識的理解。軟件環境：操作系統：windows7旗艦版集成開發環境：visualstudio2010旗艦版硬件環境：處理器：因特爾Corei3M380內存：2GB2、 實驗內容:掌握算法分析的基本方法，并結合具體的問題深入認識算法的時間復雜度分析。3、 實驗題定義一個足夠大的整型數組，并分別用起泡排序、簡單選擇排序、快速排序和歸并排序對數組中的數據進行排序（按從小到大的順序排序），記錄每種算法的實際耗時，并結合數據結構中的知識對算法的時間復雜度分析進行說明。實驗數據分兩種情況：1、數組中的數據

2、隨機生成；2、數組中的數據已經是非遞減有序。4、 實驗步驟理解算法思想和問題要求；編程實現題目要求；上機輸入和調試自己所編的程序；驗證分析實驗結果；整理出實驗報告。5、 實驗程序#include<>#include<>#include<iostream>#include<>組大小ARRAY_MAXSIZE10000如下:2 .數組大小ARRAY_MAXSIZE8000如下3 .數組大小ARRAY_MAXSIZE5000如下：6、 實驗分析1、各算法時間時間消耗圖2、各算法時間性能分析表:方法最好情況最壞情況平均情況起泡排序O(n)O(n2)O(n

3、2)快速排序O(nlog2n)O(n2)O(nlog2n)選擇排序O(n2)O(n2)O(n2)歸陽卜序O(nlog2n)O(nlog2n)O(nlog2n)3、分析與說明:由算法時間復雜度表分析，起泡排序在最好情況下時間性能好，最壞情況和平均情況和選擇排序一樣，選擇排序的時間性能都不高，均為O(n2),根據平均情況來看，快速排序和歸并排序的時間性能一樣，且最壞情況時歸并排序優于快速排序。對于隨機數組序列，數組大小為10000，8000，5000時候，歸并排序算法執行時間和快速排序時間都相對較短，簡單選擇排序緩慢，而起泡排序則是最耗時的。但是當數組由10000變到5000時，歸并排序的時間性能變化不大，而快速排序時間性能提高很多，起泡排序時間性能下降慢，所以起泡排序在隨機序列中的性能不高。對于非遞減數組序列，起泡排序時間消耗為均為0(0不代表沒耗時，只是CPUt理速度太快，沒法顯示更精確的時間

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論