时间复杂度实验

时间复杂度实验 ???????????????????? 实验一 电子2班 杨宇杰 082021083 电子2班 刘良哲 082021056 一、目:算法时间复杂度的度量 二、实验日期: 2009年9月28日星期一 三、实验目的: 掌握算法时间复杂度的理论估算和事后统计法。掌握程序的测试 方法。 四、实验地点: 中山大学南方学院H12 409房 五、实验原理及其: 1.在Microsoft Visual C++ 6.0编写一个排序程序,插入排序,～随机生成一组整数数组～然后按从小到大排列输出数组。 1 ???????????????????? 2. 对此排序算法进行充分测试。 3.估算此排序算法的时间复杂度。 4.对于不同规模的输入～统计排序程序的运行时间～并做成统计#格#～然后画出其图像。 5.比较估算的时间复杂度和统计出的复杂度～得出结论。 六、实验过程: 实验材料:电脑 网线 实验的方法:1.编写程序 #include #include #include using namespace std; #define N 1000 2 ???????????????????? void INSERTION_SORT(int a[N]) { int i,j,key; for(j=1;j=0&&a[i]>key){ a[i+1]=a[i]; i=i-1;} a[i+1]=key; } } void main() { 3 ???????????????????? int i,j,a[N]; time_t t; clock_t start,end; srand((unsigned)time(&t));//生成随机数; cout<<"随机生成的"<