时间复杂度
1.渐近紧确界记号：
$$
Θ（big-theta）
$$
2.渐近上界记号 ：
$$
O(big-oh)
$$
3.渐近下界记号 ：
$$
Ω(big-omege)
$$
4.非渐近紧确上界：
$$
o(小-oh)
$$
5.非渐近紧确下界：
$$
ω(小-omege)
$$
排序算法
插入排序
伪代码
C语言
#include<stdio.h>
int main() {
//int a[] = { 8,2,4,9,3,6 };
int n;//输入的数字个数
printf("请输入需要输入的数字的个数\n");
scanf("%d", &n);
int key,i;
printf("请输入数字\n");
int *a = (int*)malloc(n * sizeof(int));
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for (int j = 1; j < n; j++) {
key = a[j];
i = j - 1;
while (i >= 0 && a[i] > key) {
a[i + 1] = a[i];
i = i - 1;
}
a[i + 1] = key;
}
for (i = 0; i < n; i++) {
printf("%d\t", a[i]);
}
}时间复杂度为
Θ(n^2)
合并法排序
因为感觉伪代码需要大量的解释，所以本部分只贴c语言的
C语言
#include <malloc.h>
#include <stdlib.h>
#include<stdio.h>
void mergesort(int *a, int length) {
int step;
int *p, *q, *t;
int i, j, k, len1, len2;
int *temp;
step = 1;
p = a;
q = (int*)malloc(sizeof(int)*length);
temp = q;
while (step < length) {
i = 0;
j = i + step;
k = i;
len1 = i + step < length ? i + step : length;
len2 = j + step < length ? j + step : length;
while (i < length) {
while (i < len1&&j < len2) {
q[k++] = p[i] < p[j] ? p[i++] : p[j++];
}
while (i < len1) {
q[k++] = p[i++];
}
while (j < len2) {
q[k++] = p[j++];
}
i = j;
j = i + step;
k = i;
len1 = i + step < length ? i + step : length;
len2 = j + step < length ? j + step : length;
}
step *= 2;
t = p;
p = q;
q = t;
}
if (a != p) {
memcpy(a, p, sizeof(int)*length);
}
free(temp);
}
void main(void) {
int n;
printf("请输入数字的个数\n");
scanf("%d", &n);
int *a = malloc(n * sizeof(int));
printf("请输入数字\n");
for (int j = 0; j < n; j++) {
scanf("%d",&a[j]);
}
//int a[] = { 9,6,1,3,8,4,2,0,5,7 };
mergesort(a, n);
for (int i = 0; i < 10; i++) {
printf("%d ", a[i]);
}
}时间复杂度
Θ(nlgn)
主方法
$$
T(n)=aT(n/b)+f(n)
$$
二分法
斐波那契数列
定义
1，递归平方算法
Time=Θ(lgn)
2，标准算法
其实就是矩阵相乘，用for循环一个个乘然后赋值
伪代码
for i <--1 to n
do for j <-- 1 to n
do cij <-- 0
for k <-- 1 to n
do cij <-- cij + aik*bkj时间复杂度
Θ(n^3)
3，D&C 算法
原理
时间复杂度
$$
T(n)=8T(n/2)+Θ(n^2)
$$
4，strassen算法
原理
时间复杂度
$$
T(n)=7T(n/2)+Θ(n^2)
$$
快排法
伪代码
C代码
#include<stdio.h>
#include<stdlib.h>
int partitions(int *A, int p, int r) {
int x = A[r];
int i = p - 1;
int temp;
for (int j = p; j <= r - 1; j++) {
if (A[j] <= x) {
i = i + 1;
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
temp = A[i + 1];
A[i + 1] = A[r];
A[r] = temp;
return i + 1;
}
void quicksort(int *A, int p, int r) {
int q;
if (p < r) {
q = partitions(A, p, r);
quicksort(A, p, q - 1);
quicksort(A, q + 1, r);
}
}
int main() {
int A[1000] = { 0 };
int length;
printf("请输入数字的个数\n");
scanf("%d", &length);
printf("请输入数字\n");
for (int i = 0; i < length; i++)
scanf("%d", &A[i]);
quicksort(A, 0, length - 1);
for (int i = 0; i < length; i++)
printf("%d", A[i]);
}时间复杂度
最坏情况：Θ(n^2)
最佳情况：Θ(nlgn)
平衡情况：Θ(nlgn)
随机分治法
伪代码
c语言代码
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
int partition(int *A, int p, int r) {
int x = A[r];
int i = p - 1;
int temp;
for (int j = p; j <= r - 1; j++) {
if (A[j] <= x) {
i = i + 1;
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
temp = A[i + 1];
A[i + 1] = A[r];
A[r] = temp;
return i + 1;
}
int select(int *A,int p,int q,int i) {
int r,k;
if (p == q) {
return A[p];
}
r = partition(A, p, q);
k = r - p + 1;
if (i == k) {
return A[r];
}
if (i < k) {
return select(A, p, r - 1, i);
}
else {
return select(A, r + 1, q, i - k);
}
}
int main() {
int n,k;
int A[100];
printf("请输入元素的个数\n");
scanf("%d", &n);
printf("请输入元素\n");
for (int i = 0; i < n; i++) {
scanf("%d", &A[i]);
}
printf("请输入你想查找的第K大元素");
scanf("%d", &k);
printf("%d",select(A, 0, n - 1, k));
}
