你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

时间复杂度

2021-11-23 18:53:39

时间复杂度:算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。(总的来说,运行所需要的时间快慢,这里的时间快慢是相对的,那排序举例:如果用一段相同的代码且代码较少,我们没必要用复杂的排序,但代码太大,我们就得用复杂的排序来缩短时间。如果还是不懂的话,那就转化为数学模型,把不同的算法看成不同的幂函数,有的幂函数前期y值大,有的幂函数后期y值大)。

例:

蒜头君手上有个长度为 n 的数组 A。由于数组实在太大了,所以蒜头君也不知道数组里面有什么数字,所以蒜头君会经常询问整数 x 是否在数组 A 中。

输入格式
第一行输入两个整数 n 和 m,分别表示数组的长度和查询的次数。

接下来一行有 n 个整数 a1.

接下来 m 行,每行有 1 个整数 x,表示蒜头君询问的整数。

输出格式
对于每次查询,如果可以找到,输出"YES",否则输出"NO"。

数据范围
1≤n,m≤10的5次方,0≤x≤10的6次方。
我只展示算法一段。

快速排序

#include <stdio.h>

void quickSort(int left, int right, int a[]) { //快速排序
	int key, low, high, s, j, temp;

	if (left >= right) { //当左边大于右边返回主函数
		return;
	}

	key = a[left];
	low = left;
	high = right;
	while (low < high) {
		while (low < high && a[high] >= key) {
			high --;
		}

		while (low < high && a[low] <= key) {
			low ++;
		}
		if (low < high) {
			temp = a[low];
			a[low] = a[high];
			a[high] = temp;
		}
	}//随意找一个数,将小于这个数的排在左边大于这个数的排在右边
	a[left] = a[low];
	a[low] = key;
	s = low - 1;
	j = low + 1;
	quickSort(left, s, a); //以这个数左边的数在进行一次排序
	quickSort(j, right, a); //以这个数右边的数在进行一次排序
}

int main() {
	int n, g, x, h = 0, z = 0, i = 0, num, num1, judge, left, right, mid, temp;
	scanf("%d", &n);

	int str1[n];
	while (1) {
		scanf("%d", &num);
		char c = getchar();
		str1[i++] = num;
		if (c == '\n') {
			break;
		}
	}
	x = n - 1;
	quickSort(0, x, str1);

	for (i = 0; i < n; i++) {
		printf("%d ", str1[i]);
	}
}

桶排序:

#include <stdio.h>

int main() {
	int n, t, i, j;
	scanf("%d", &n);
	long long a[n];
	for (i = 0; i < n; i++) {
		a[i] = 0;
	}
	for (i = 0; i < n; i++) {
		scanf("%d", &t);
		a[t]++;
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < a[i]; j++) {
			printf("%d ", i);
		}
	}
}

冒泡排序:

#include <stdio.h>

int main() {
	int n, t, i, j, temp;;
	scanf("%d", &n);
	long long a[n] = {0};
	for (t = 0; t < n; t++) {
		scanf("%d", &a[t]);
	}
	for (i = 1; i <= n - 1; i++) { //外层循环是比较的轮数,数组内有10个数,那么就应该比较10-1=9轮
		for (j = 0; j <= n - 1 - i; j++) { //内层循环比较的是当前一轮的比较次数,例如:第一轮比较9-1=8次,第二轮比较9-2=7次
			if (a[j] > a[j + 1]) { //相邻两个数如果逆序,则交换位置
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
	for (i = 0; i < n; i++)
		printf("%-4d", a[i]);
	printf("\n");
}

而这个题所排序数组中的数无穷多个,我们要考虑是否超限和是否超时(这里要关注时间复杂度),可以将这些代码复制下来试一试,比较一下数字少时所运行的时间和数字多时所运行的时间。