算法实验2.2、2.3

2.2主要内容

比较快速排序，归并排序以及堆排序算法的时间效率。了解影响算法执行时间的 主要因素以及如何降低算法的执行时间。 

#include<iostream>
using namespace std;
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<time.h>
#include <sys/timeb.h>
#include"string.h"
#pragma warning(disable : 4996)

typedef struct RedType {
	int key;
}RedType;
typedef struct SqList {
	RedType* r;
	int Length;
}SqList;

SqList* CreateRandomSqList(int sqListLen) {
	SqList* sq;
	int i;
	sq = (SqList*)malloc(sizeof(SqList));
	//输入序列长度
	sq->Length = sqListLen;
	sq->r = (RedType*)malloc(sizeof(RedType) * (sq->Length + 1)); //给序列的每个元素分配空间
	srand((unsigned)(time(NULL)));
	for (i = 1; i <= sq->Length; i++) {
		sq->r[i].key = int(rand());
	}
	return sq;  //返回序列起始地址
}
//创建一个与csp一样的存储空间
SqList* CopyRandomSqList(SqList* csp) {
	SqList* sq;
	int i;
	sq = (SqList*)malloc(sizeof(SqList));
	//输入序列长度
	sq->Length = csp->Length;
	sq->r = (RedType*)malloc(sizeof(RedType) * (sq->Length + 1)); //给序列的每个元素分配空间
	for (i = 1; i <= sq->Length; i++) {
		sq->r[i].key = csp->r[i].key;
	}
	return sq;  //返回序列起始地址
}
void WritetoFile(int num, int sortTime[], FILE* fp) {
	char ch[20];
	for (int i = 0; i < num; i++) {
		_itoa_s(sortTime[i], ch, 10);
		strcat_s(ch, ",");
		fwrite(ch, sizeof(char), strlen(ch), fp);
	}
	fwrite("\n", sizeof(char), 1, fp);
}

//快速排序
void QuickSort(RedType q[], int l, int r) {
	if (l >= r)return;
	int i = l - 1, j = r + 1, x = q[l + r >> 1].key;
	while (i < j) {
		do i++; while (q[i].key < x);
		do j--; while (q[j].key > x);
		if (i < j)swap(q[i].key, q[j].key);
	}
	QuickSort(q, l, j);
	QuickSort(q, j + 1, r);
}
//堆排序
void HeapAdjust(RedType* SR, int s, int m)//一次筛选的过程
{
	int rc, j;
	rc = SR[s].key;
	for (j = 2 * s; j <= m; j = j * 2)//通过循环沿较大的孩子结点向下筛选
	{
		if (j < m&& SR[j].key < SR[j + 1].key) j++;//j为较大的记录的下标
		if (rc > SR[j].key) break;
		SR[s] = SR[j]; s = j;
	}
	SR[s].key = rc;//插入
}
void HeapSort(RedType* SR, int n)
{
	int temp, i, j;
	for (i = n / 2; i > 0; i--)//通过循环初始化顶堆
	{
		HeapAdjust(SR, i, n);
	}
	for (i = n; i > 0; i--)
	{
		temp = SR[1].key;
		SR[1].key = SR[i].key;
		SR[i].key = temp;//将堆顶记录与未排序的最后一个记录交换
		HeapAdjust(SR, 1, i - 1);//重新调整为顶堆
	}
}
//归并排序
void aMerge(RedType* SR, int i, int m, int n) {
	int j, k;
	for (j = m + 1; j <= n; j++) {
		if (SR[j].key <= SR[j - 1].key) {
			int temp = SR[i].key;
			for (k = j - 1; temp < SR[k].key && k >= i; --k)
				SR[k + 1].key = SR[k].key;
			SR[k + 1].key = temp;
		}
	}
	return;
}
void aMSort(RedType* SR, int s, int t)
{
	if (s < t) {
		int mid = (s + t) / 2;
		aMSort(SR, s, mid);
		aMSort(SR, mid + 1, t);
		aMerge(SR, s, mid, t);
	}
	return;
}
void MergeSort(SqList* L) {
	aMSort(L->r, 1, L->Length);
	return;
}

int main() {

	SqList* L, * L1, * L2;
	struct __timeb64 stime, etime;
	long int rmtime, rstime;
	char ch[20];
	int quickSortTime[105], mergeSortTime[105], heapSortTime[105];
	FILE* fp;
	fp = fopen("Curv.csv", "w");

	for (int i = 10000; i <= 1000000; i = i + 10000) {
		_itoa_s(i, ch, 10);
		strcat_s(ch, ",");
		fwrite(ch, sizeof(char), strlen(ch), fp);
	}
	fwrite("\n", sizeof(char), 1, fp);
	int k = 0;
	for (int i = 10000; i <= 1000000; i = i + 10000) {
		L = CreateRandomSqList(i);
		L1 = CopyRandomSqList(L);
		L2 = CopyRandomSqList(L);
		//归并排序
		_ftime64_s(&stime);
		MergeSort(L);
		_ftime64_s(&etime);
		free(L->r);
		free(L);
		rstime = etime.time - stime.time;
		rmtime = rstime * 1000;
		rmtime += etime.millitm - stime.millitm;
		mergeSortTime[k] = rmtime;

		//快速排序
		_ftime64_s(&stime);
		QuickSort(L1->r, 0, L1->Length - 1);
		_ftime64_s(&etime);
		free(L1->r);
		free(L1);
		rstime = etime.time - stime.time;
		rmtime = rstime * 1000;
		rmtime += etime.millitm - stime.millitm;
		quickSortTime[k] = rmtime;

		//堆排序
		_ftime64_s(&stime);
		HeapSort(L2->r, L2->Length - 1);
		_ftime64_s(&etime);
		free(L2->r);
		free(L2);
		rstime = etime.time - stime.time;
		rmtime = rstime * 1000;
		rmtime += etime.millitm - stime.millitm;
		heapSortTime[k] = rmtime;
		k++;
	}
	WritetoFile(100, mergeSortTime, fp);
	WritetoFile(100, quickSortTime, fp);
	WritetoFile(100, heapSortTime, fp);
	fclose(fp);
	return 1;
}

2.3主要内容 

 学习分析递归程序结构的时间复杂度和影响算法运行时间的因素。

#include<iostream>
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<time.h>
#include <sys/timeb.h>
#include"string.h"
#pragma warning(disable : 4996)
#define M 4
#define N 15
using namespace std;

class Color {
	friend int mColoring(int, int, int**);
public:
	bool Ok(int k);
	void Backtrack(int k);
	int n, m, ** a, * x;
	long sum;
};
long long  cifang(int n,int m)
{
	int count = 0;long long c = 1;
	for (int i = 0; i < n; i++)
	{

		c = c*(m/2);//防止时间复杂度太大了，进行缩小
		count++;
	}
	return c;
}
void WritetoFile(int num, int sortTime[], FILE* fp) {
	char ch[20];
	for (int i = 0; i < num; i++) {
		_itoa_s(sortTime[i], ch, 10);
		strcat_s(ch, ",");
		fwrite(ch, sizeof(char), strlen(ch), fp);
	}
	fwrite("\n", sizeof(char), 1, fp);
}
int mColoring(int, int, int**);
int main() {
	int n, m, ** a, sum; long long timecom{ 0 };
	//cout << "Please input the number of colors:";
	//cin >> m;

	struct __timeb64 stime, etime;
	long int rmtime, rstime;
	char ch[20];
	int paintTime[105]{0};
	FILE* fp;
	fp = fopen("Curv.csv", "w");

	for (int i = 5; i <= N; i = i + 1) {
		_itoa_s(i, ch, 10);
		strcat_s(ch, ",");
		fwrite(ch, sizeof(char), strlen(ch), fp);
	}
	fwrite("\n", sizeof(char), 1, fp);

	int k{ 0 };
	/*for (int i = 5; i <= N; i = i + 1) {

		//cout << "Please input the number of nodes:";
		n=i;
		a = new int* [n + 1];
		for (int i = 0; i <= n; i++) {
			a[i] = new int[n + 1];
		}
		//cout << "Please input the ralation of nodes:1-->Connected,0-->Not connected";
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				//cout << "please input the ralation of" << i << "and" << j << ":";
				//cin >> a[i][j];
				//a[i][j] = 1;//完全图,最外面的i循环换成 i <= M，注意要改四处
				a[i][j] = 0;//一条边都没有，最外面的i循环换成 i <= N
				a[j][i] = a[i][j];
			}
		}
		_ftime64_s(&stime);

		sum = mColoring(n, M, a);

		_ftime64_s(&etime);

		rstime = etime.time - stime.time;
		rmtime = rstime * 1000;
		rmtime += etime.millitm - stime.millitm;
		paintTime[k] = rmtime;
		k++;

		delete[]a;
	}

	WritetoFile(11, paintTime, fp);

	for (int i = 5; i <= N; i = i + 1)
	{
		timecom = i * cifang(i,M);

		_itoa_s(timecom, ch, 10);
		strcat_s(ch, ",");
		fwrite(ch, sizeof(char), strlen(ch), fp);
	}
	fwrite("\n", sizeof(char), 1, fp);*/

	k = 0;
	n = 10;
	for (int j = 5; j <= N; j = j + 1) {

		//cout << "Please input the number of nodes:";
		m = j;
		a = new int* [n + 1];
		for (int i = 0; i <= n; i++) {
			a[i] = new int[n + 1];
		}
		//cout << "Please input the ralation of nodes:1-->Connected,0-->Not connected";
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				//cout << "please input the ralation of" << i << "and" << j << ":";
				//cin >> a[i][j];
				//a[i][j] = 1;//完全图，注意要改四处
				a[i][j] = 0;//一条边都没有
				a[j][i] = a[i][j];
			}
		}
		_ftime64_s(&stime);

		sum = mColoring(n, m, a);

		_ftime64_s(&etime);

		rstime = etime.time - stime.time;
		rmtime = rstime * 1000;
		rmtime += etime.millitm - stime.millitm;
		paintTime[k] = rmtime;
		k++;

		delete[]a;
	}

	WritetoFile(11, paintTime, fp);

	for (int i = 5; i <= N; i = i + 1)
	{
		timecom = n * cifang(n,i);

		_itoa_s(timecom, ch, 10);
		strcat_s(ch, ",");
		fwrite(ch, sizeof(char), strlen(ch), fp);
	}
	fwrite("\n", sizeof(char), 1, fp);

	fclose(fp);

	//cout << sum << endl;
	return 1;
}
bool Color::Ok(int k)
{
	for (int j = 1; j <= n; j++)
		if ((a[k][j] == 1 && x[j] == x[k]))
			return false;
	return true;
}
void Color::Backtrack(int t) {
	if (t > n) {
		sum++;
		/*for (int i = 1; i <= n; i++)
			cout << x[i] << " ";
		cout << endl;*/
	}
	else {
		for (int i = 1; i <= m; i++) {
			x[t] = i;
			if (Ok(t))Backtrack(t + 1);
			x[t] = 0;
		}
	}
}
int mColoring(int n, int m, int** a) {
	Color X;
	X.n = n;
	X.m = m;
	X.a = a;
	X.sum = 0;
	int* p = new int[n + 1];
	for (int i = 0; i <= n; i++)p[i] = 0;
	X.x = p;
	X.Backtrack(1);
	delete[]p;
	return X.sum;
}

时间复杂度分析：

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/763484.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

vue全局方法plugins/utils

vue全局方法plugins/utils

一、在src目录下创建一个plugins文件夹 test.ts文件存放创建的方法&#xff0c;index.ts用于接收所有自定义方法进行统一处理 二、编写自定义方法 // test.ts文件 export default {handleTest(val1: number, val2: number) {// 只是一个求和的方法return val1 val2;}, };三…
阅读更多...
MySQL数据库的主从复制与读写分离

MySQL数据库的主从复制与读写分离

一、MySQL数据库的主从复制 1.主从复制的概述及原理 &#xff08;1&#xff09;主从复制的意义 在实际的生产环境中&#xff0c;如果对数据库的读和写都在同一个数据库服务器中操作,无论是在安全性、高可用性还是高并发等各个方面都是完全不能满足实际需求的。因此&#xff…
阅读更多...
C语言之进程的学习2

C语言之进程的学习2

互斥锁&#xff1a;
阅读更多...
【Nvidia+AI相机】涂布视觉检测方案专注提高锂电池质量把控标准

【Nvidia+AI相机】涂布视觉检测方案专注提高锂电池质量把控标准

锂电池单元的质量在多个生产制造领域都至关重要&#xff0c;特别是在新能源汽车、高端消费电子等行业。这些领域的产品高度依赖锂电池提供持续、稳定的能量供应。优质的锂电池单元不仅能提升产品的性能和用户体验&#xff0c;还能确保使用安全。因此&#xff0c;保证锂电池单元…
阅读更多...
微信小程序template模板引入

微信小程序template模板引入

如图&#xff1a;temp.wxml是template引入的模板 在two.wxml中&#xff1a; import&#xff1a;是引入temp的页面让template中的内容显示出来在two页面中&#xff1b; include:是显示temp页面内容不在template包裹&#xff0c;template以外的view标签文字和不在view的文字让…
阅读更多...
探索PcapPlusPlus开源库：网络数据包处理与性能优化

探索PcapPlusPlus开源库：网络数据包处理与性能优化

文章目录 0. 本文概要1. PcapPlusPlus介绍1.1 概述1.2主要特性和功能1.3 PcapPlusPlus 主要模块关系和依赖1.4 网络协议层处理过程 2. 实例2.1 基于 PcapPlusPlus 的应用程序设计和封装流程&#xff1a;2.2 多线程示例代码2.3 代码说明&#xff1a; 3. 程序性能进一步优化3.1 避…
阅读更多...
Golang内存分配

Golang内存分配

Go内存分配语雀笔记整理 Golang内存模型设计理念思考核心代码阅读mspanmcachemcentral中心缓存mheap分配过程 Golang内存模型设计理念思考 golang内存分配基于TCmalloc模型&#xff0c;它核心在于&#xff1a;空间换时间&#xff0c;一次缓存&#xff0c;多次复用&#xff1b;…
阅读更多...
基于x86+FPGA+AI轴承缺陷视觉检测系统，摇枕弹簧智能检测系统

基于x86+FPGA+AI轴承缺陷视觉检测系统，摇枕弹簧智能检测系统

一、承缺陷视觉检测系统 应用场景 轴类零件自动检测设备&#xff0c;集光、机、软件、硬件&#xff0c;智能图像处理等先进技术于一体&#xff0c;利用轮廓特征匹配&#xff0c;目标与定位&#xff0c;区域选取&#xff0c;边缘提取&#xff0c;模糊运算等算法实现人工智能高…
阅读更多...
Linux 高级编程——线程控制

Linux 高级编程——线程控制

线程控制&#xff1a;互斥与同步 概念&#xff1a; 互斥 》在多线程中对临界资源的排他性访问。 互斥机制 》互斥锁 》保证临界资源的 访问控制。 pthread_mutex_t mutex; 互斥锁类型 互斥锁变量 内核对象 框架&#xff1a; 定义互斥锁 》初始化锁 》加…
阅读更多...
Kafka-服务端-副本同步-源码流程

Kafka-服务端-副本同步-源码流程

杂 在0.9.0.0之前&#xff0c;Kafka提供了replica lag.max.messages 来控制follower副本最多落后leader副本的消息数量&#xff0c;follower 相对于leader 落后当超过这个数量的时候就判定该follower是失效的&#xff0c;就会踢出ISR&#xff0c;这里的指的是具体的LEO值。 对…
阅读更多...
Hadoop权威指南-读书笔记-01-初识Hadoop

Hadoop权威指南-读书笔记-01-初识Hadoop

Hadoop权威指南-读书笔记 记录一下读这本书的时候觉得有意思或者重要的点~ 第一章—初识Hadoop Tips&#xff1a; 这个引例很有哲理嘻嘻&#x1f604;&#xff0c;道出了分布式的灵魂。 1.1 数据&#xff01;数据&#xff01; 这一小节主要介绍了进入大数据时代&#xff0c;面…
阅读更多...
【windows|012】光猫、路由器、交换机详解

【windows|012】光猫、路由器、交换机详解

&#x1f341;博主简介&#xff1a; &#x1f3c5;云计算领域优质创作者 &#x1f3c5;2022年CSDN新星计划python赛道第一名 &#x1f3c5;2022年CSDN原力计划优质作者 ​ &#x1f3c5;阿里云ACE认证高级工程师 ​ &#x1f3c5;阿里云开发者社区专家博主 &#x1f48a;交流社…
阅读更多...
QML学习——Qt Quick Extras Examples 1.4（八）

QML学习——Qt Quick Extras Examples 1.4（八）

Qt Quick Extras Examples 阅读官方的源码然后尝试做了下 01 A car dashboard 样例演示&#xff1a; 说明&#xff1a; ValueSource组件控制数值相关的动画&#xff0c;例如图中数值的变化&#xff1b;TurnIndicator组件是控制左右方向灯的闪烁和背景&#xff0c;里面使用…
阅读更多...
excel修改批量一列单价的金额并保留1位小数

excel修改批量一列单价的金额并保留1位小数

1.打开表格&#xff0c;要把单价金额变成现在的两倍&#xff0c;数据如下&#xff1a; 2.把单价这一列粘贴到一个新的sheet页面&#xff0c;在B2单元格输入公式&#xff1a;A2*2 然后按enter回车键,这时候吧鼠标放到B2单元格右下角&#xff0c;会出现一个黑色的小加号&#xf…
阅读更多...
SQL 注入联合查询之为什么要 and 1=2

SQL 注入联合查询之为什么要 and 1=2

在 SQL 注入联合查询中&#xff0c;将 id 先置为假&#xff08;如 id-1 或其他使查询结果为空的条件&#xff09;&#xff0c;通常是为了让前面的查询语句查询不到结果&#xff0c;从而使联合查询中后面的语句结果能够显示在回显位上
阅读更多...
【深度学习】pytorch训练中的一个大坑

【深度学习】pytorch训练中的一个大坑

使用的命令&#xff1a;iostat -x 5 可以看到 ssd的利用率已经满了。 之前在的数据集放在了 hdd上&#xff0c;训练结果特别慢。 所以我把它移动到了ssd上&#xff0c;然后训练参数用的 resume&#xff0c; 但是&#xff01;&#xff01;&#xff01;&#xff01;它把历史记住…
阅读更多...
虚拟环境管理

虚拟环境管理

虚拟环境 在使用 Python 时我们一般使用“pip install 第三方包名”来安装第三方包&#xff0c;但是由于pip的特性&#xff0c;系统只能安装每个包的一个版本。而在实际开发中&#xff0c;可能同时开发多个项目&#xff0c;如&#xff1a;上图有三个项目&#xff1b;每个项目需…
阅读更多...
摄影后期色彩管理流程（Lightroom篇）

摄影后期色彩管理流程（Lightroom篇）

在摄影后期处理中&#xff0c;色彩管理是确保图像从捕捉到输出的一致性和准确性的关键。Lightroom 和 Photoshop 其实已经将这套色彩管理流程作为默认选项&#xff0c;如果实质操作时仍存在色彩偏差的问题&#xff0c;可参考以下内容。 ProPhoto RGB > Adobe RGB > sRGB …
阅读更多...
幻兽帕鲁服务器如何安装模组安装

幻兽帕鲁服务器如何安装模组安装

由于模组多数为Window版本的&#xff0c;所以本教程以服务端为Window的作为演示&#xff08;Linux服务端的也是一样的操作&#xff09;百度莱卡云开服 如果你你是Linux版本的&#xff0c;请点击跳转切换服务端教程 接下来是本地安装模组包的方法&#xff08;服务器自带&#xf…
阅读更多...
Web3 游戏周报（6.23 - 6.29）

Web3 游戏周报（6.23 - 6.29）

区块链游戏热度不减&#xff0c;你是否掌握了上周的重要动态&#xff1f; 回顾上周区块链游戏动态&#xff0c;查看 Footprint Analytics 与 ABGA 的最新数据报告。 【6.23 - 6.29】Web3 游戏行业动态&#xff1a; 继 Notcoin 之后&#xff0c;另一款 Telegram 游戏 Hamster …
阅读更多...
最新文章

Copyright @ 2022~2023