算法实验报告-分治法性能分析.doc
文本预览下载声明
分治法算法分析作业 吴迪2011-3-29
本次是第一次算法作业,该部分内容包含3个题目的程序代码,分析文档,说明图片等内容
目录
TOC \o 1-3 \h \z \u
HYPERLINK \l _Toc289198677 引言 PAGEREF _Toc289198677 \h 3
HYPERLINK \l _Toc289198678 1算法性能比较 PAGEREF _Toc289198678 \h 3
HYPERLINK \l _Toc289198679 1.1问题分析 PAGEREF _Toc289198679 \h 3
HYPERLINK \l _Toc289198680 1.2源程序代码 PAGEREF _Toc289198680 \h 3
HYPERLINK \l _Toc289198681 1.3运行示例 PAGEREF _Toc289198681 \h 8
HYPERLINK \l _Toc289198682 1.4数据分析 PAGEREF _Toc289198682 \h 8
HYPERLINK \l _Toc289198683 (单次录入数据具有较大随机误差,只看增长趋势) PAGEREF _Toc289198683 \h 8
HYPERLINK \l _Toc289198684 2循环赛问题 PAGEREF _Toc289198684 \h 9
HYPERLINK \l _Toc289198685 2.1问题描述 PAGEREF _Toc289198685 \h 9
HYPERLINK \l _Toc289198686 2.2问题分析 PAGEREF _Toc289198686 \h 9
HYPERLINK \l _Toc289198687 2.3 源程序 PAGEREF _Toc289198687 \h 10
HYPERLINK \l _Toc289198688 2.4运行示例 PAGEREF _Toc289198688 \h 11
HYPERLINK \l _Toc289198689 3最大最小值问题 PAGEREF _Toc289198689 \h 12
HYPERLINK \l _Toc289198690 3.1问题描述与分析 PAGEREF _Toc289198690 \h 12
HYPERLINK \l _Toc289198691 3.2源程序 PAGEREF _Toc289198691 \h 13
HYPERLINK \l _Toc289198692 3.3运行示例 PAGEREF _Toc289198692 \h 14
引言
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。分治法是计算机科学中经常使用的一种算法。设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。但是不是所有问题都适合用分治法解决。当求解一个输入规模为n且取值又相当大的问题时,使用蛮力策略效率一般得不到保证。因此分治策略将问题划分成k个子问题分别求解合并能有效提高计算效率。
1算法性能比较
1.1问题分析
比较插入排序,合并排序和快速排序性能。
算法性能比较通常是从时间复杂度的角度进行的。排序算法的复杂度主要和算法中的比较次数和元素交换或移动次数有关。因而在不同大小规模的问题中通过统计这两者之和来评判算法的优劣。
同时也可以证明各种算法的时间复杂度与问题规模n之间的关系。
特别说明:本程序中考虑到不同规模的乱序数据输入过程比较复杂,编写了一个规模n的整型数据随机排列函数,能够直接生成指定大小的1-n无序整数列。
1.2源程序代码
//2011年3月19日0:20:02
//main test.cpp for test
#includeiostream
#includetime.h
using namespace std;
//全局标记比较次数和移动次数
int count_compare=0;
int count_move = 0;
int count_all(){
return count_compare+count_move;
}
void clear_count()
{
count_compare=0;
count_move = 0;
}
//insert sort
v
显示全部