时间复杂度:算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大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");
}
而这个题所排序数组中的数无穷多个,我们要考虑是否超限和是否超时(这里要关注时间复杂度),可以将这些代码复制下来试一试,比较一下数字少时所运行的时间和数字多时所运行的时间。