计算资源
时间复杂度:
程序运行需要的时间。
空间复杂度:
程序运行需要的存储空间。
说明
1、定义全局数组无限制,且自动初始化为0或NULL;
2、main函数栈空间为8MB, 可定义整形数组大小 <= 2000000位,1整形 = 4字节 = 32位二进制;
3、笔记本电脑的计算能力大约每秒千万次数量级;而oj系统每秒能运行1亿次;
时间计算
#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
int main() {
int k = 0, n = 1e8;
clock_t start, end;
start = clock(); // 开始
for (int i = 0; i < n; i++) ++k;
end = clock(); // 结束
cout << "t = " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;
return 0;
}
/*
时间复杂度分析:
循环n次,运行效率为线性时间,即 O(n);
在CPU为i5-8250U、内存为8GB、64位操作系统下:
n = 1e8时, t = 0.164s;
n = 19e时, t = 1.645s;
*/
下用一道例题为例
hdu1425 “sort”
链接: http://acm.hdu.edu.cn/showproblem.php?pid=1425
思路:对100万个数排序,再输出前 m 大的数。
//法一冒泡排序
#include <bits/stdc++.h>
using namespace std;
int a[1000001];
#define swap(a, b) {a ^= b; b ^= a; a ^= b;}
int n, m;
void bubble_sort() {
for (int i = 1; i < n; i++) {
for (int j = 1; j <= n - i; j++) {
if (*(a + j) > *(a + j + 1))
swap(*(a + j), *(a + j + 1));
}
}
}
int main() {
while (~scanf("%d %d", &n, &m)) {
for (int i = 1; i <= n; i++) scanf("%d", a + i); // 数据太多只能用 scanf 输入;
bubble_sort();
for (int i = n; i >= n - m + 1; i--) {
if (!(i ^ (n - m + 1))) printf("%d\n", *(a + i));
else printf("%d ", *(a + i));
}
memset(a, 0, sizeof(a));
}
return 0;
}
/*
分析:
时间复杂度
bubble_sort()函数有两重循环,循环次数为 n-1 + n-2 + n-3 + ... + 1 = n^2 / 2; 而在swap(a, b)执行了3次操作;总计算次数为 3n^2 / 2;复杂度记为 O(n*n); 故 n < 10000 冒泡排序才勉强过;
空间复杂度
程序使用 int a[1000001]存储数据,且 bubble_sort() 没有使用额外空间,故约使用 4MB 空间;
// 法二 快速排序
#include <bits/stdc++.h>
using namespace std;
int a[1000001];
#define swap(a, b) {a ^= b; b ^= a; a ^= b;}
int n, m;
int main() {
while (~scanf("%d %d", &n, &m)) {
for (int i = 1; i <= n; i++) scanf("%d", a + i);
sort(a + 1, a + n + 1);
for (int i = n; i >= n - m + 1; i--) {
if (!(i ^ (n - m + 1))) printf("%d\n", *(a + i));
else printf("%d ", *(a + i));
}
memset(a, 0, sizeof(a));
}
return 0;
}
基于STL的 sort() 函数,是改良版的快速排序;
时间复杂度为O(nlgn); 正好通过,提交运行时间为600ms;
//法三哈希排序
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000001
int a[MAXN];
int main() {
int n, m;
while (~scanf("%d %d", &n, &m)) {
for (int i = 0; i < n; i++) {
int t;
scanf("%d", &t);
a[500000 + t] = 1; // 数字t登记在 t + 500000的位置
}
for (int i = MAXN - 1; m > 0; i--) {
if (*(a + i)) {
if (m > 1) printf("%d ", i - 500000);
else printf("%d\n", i - 500000);
--m;
}
}
memset(a, 0, sizeof(a));
}
return 0;
}
思路:
在输入数字t的时候,在a[500000 + t] 这个位置记录a[500000 + t] = 1 记录 t ,在输出的时候逐个检查 a[i] , if (a[i] == 1) 表示这个数存在, 打印出前 m 个数;
哈希排序以空间换时间,时间复杂度为O(n), 比快排快;
在 hdu 提交运行时间 500ms ;
算法的选择
对于一个问题必有多种解法, 低效算法编码时间往往低于高效算法编码时间。
算法的定义与评估
1、定义:在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。
算法的时间复杂度,也就是算法的时间度量,记作:T(n) = O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,称为时间复杂度。其中f(n)是问题规模n的某个函数。
2、推导大O阶方法
推导大O阶:
1、用常数1取代运行时间中的所有加法常数
2、在修改后的运行次数函数中,只保留最高阶项
3、如果最高阶项存在且不是i,则去除与这个项相乘的常数得到的结果就是大O阶
3、常见的时间复杂度
执行次数函数 | 阶 | 非正式术语 |
---|---|---|
12 | O(1) | 常数阶 |
2n+3 | O(n) | 线性阶 |
3n^2+2n+1 | O(n^2) | 平方阶 |
5log2n+19 | O(logn) | 对数阶 |
2n+3nlog2n+19 | O(nlogn) | nlogn阶 |
6n3+2n2+3n+4 | O(n^3) | 立方阶 |
2^n | O(2^n) |
常用时间复杂度所耗费的时间从小到大依次是:
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < (n!) < O(n^n);
N^3以后都不应该出现在算法中。
4、最坏情况和平均情况:
最坏情况运行时间是一种保证,那就是运行时间不会再坏了,在应用中,这是一种最重要的需求,通常,除非特别指定,我们提到的运行时间都是最坏情况运行时间