没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
算法的时间复杂度
一、实验目的与要求:
熟悉 C/C++语言的集成开发环境;
通过本实验加深对算法分析基础知识的理解。
二、实验内容:
掌握算法分析的基本方法,并结合具体的问题深入认识算法的时间复杂度分析。
三、实验题:
定义一个足够大的整型数组,并分别用起泡排序、简单选择排序、快速排序和归并排序对
数组中的数据进行排序(按从小到大的顺序排序),记录每种算法的实际耗时,并结合数
据结构中的知识对算法的时间复杂度分析进行说明。实验数据分两种情况:
1、数组中的数据随机生成;
2、数组中的数据已经是非递减有序。
四、实验步骤
理解算法思想和问题要求;
编程实现题目要求;
上机输入和调试自己所编的程序;
验证分析实验结果;
整理出实验报告。
五、实验程序
1、 起泡排序十万元素数组:
//实验题目;测试起泡排序的运行时间
//完成时间:2010/10/28 16:58
//运行环境:windows XP VC++ 6.0
//硬件:CPU 2.80GHz
#include<iostream>
using namespace std;
#include<cstdlib>
//using std::rand;
//using std::srand;
#include<ctime>
//using std::time;
void InitArray( int[], int );
void BubbleSort( int[] , int);
void Display100Elements( int[] );
int main()
{
clock_t starttime1, endtime1, starttime2, endtime2;
const int arraySize = 100000;
int array[arraySize];
InitArray( array, arraySize );
cout << "该数组起泡排序前,前 100 个元素:" << endl;
Display100Elements( array );
starttime1 = clock();
BubbleSort( array, arraySize );
endtime1 = clock();
cout << "该数组起泡排序后,前 100 个元素:" << endl;
Display100Elements( array );
cout << "含" << arraySize <<"个随机元素数组起泡排序(升序)运行时间:"
<< showpoint
<< (double)(endtime1 - starttime1) / CLOCKS_PER_SEC<<"秒\n"<<endl;
starttime2 = clock();
BubbleSort( array, arraySize );
endtime2 = clock();
cout << "含" << arraySize <<"个非递减有序元素数组起泡排序(升序)运行时间:"
<< showpoint
<< (double)(endtime2 - starttime2) / CLOCKS_PER_SEC<<"秒\n"<<endl;
return 0;
}
void InitArray( int a[], int arraySize )
{
srand(time(0));
for(int i = 0; i < arraySize; i++)
a[i] = rand();
cout << "含" << arraySize << "个随机元素的数组已经被初始化\n" << endl;
}
void BubbleSort( int a[] , int arraySize )
{
int exchange = arraySize - 1;
while(exchange != 0) //仅当上一趟排序有交换时才进行本趟排序
{
int bound = exchange; exchange = 0;
for ( int i = 0; i < bound; i++ )
if(a[i] > a[i+1])
{
int temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
exchange = i; //记录每一次发生交换的元素位置
}
}
}
void Display100Elements( int a[] )
{
for (int i = 0; i < 100; i++)
{
cout << a[i] <<" ";
if ( i%10 == 9) cout << endl;
}
cout << endl;
}
2、简单选择排序十万元素数组:
//实验题目;测试简单选择排序的运行时间
//完成时间:2010/10/28 23:41
//运行环境:windows XP VC++ 6.0
//硬件: CPU 2.80Ghz
#include<iostream>
using namespace std;
#include<cstdlib>
//using std::rand;
//using std::srand;
#include<ctime>
//using std::time;
void InitArray( int[], int );
void SlectSort( int[] , int);
void Display100Elements( int[] );
int main()
{
clock_t starttime1, endtime1, starttime2, endtime2;
const int arraySize = 100000;
int array[arraySize];
InitArray( array, arraySize );
cout << "该数组简单选择排序前,前 100 个元素:" << endl;
Display100Elements( array );
starttime1 = clock();
SlectSort( array, arraySize );
endtime1 = clock();
cout << "该数组简单选择排序后,前 100 个元素:" << endl;
Display100Elements( array );
cout << "含" << arraySize <<"个随机元素数组简单选择排序(升序)运行时间:"
<< showpoint
<< (double)(endtime1 - starttime1) / CLOCKS_PER_SEC<<"秒\n"<<endl;
starttime2 = clock();
SlectSort( array, arraySize );
endtime2 = clock();
cout << "含" << arraySize <<"个非递减有序元素数组简单选择排序(升序)运行时
间:"
剩余15页未读,继续阅读
资源评论
qq957252834
- 粉丝: 0
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功