AKSZ - 第1/2课笔记
2024-05-29 17:45:30
发布于:广东
算法入门
算法是什么
算法: 一组用于解决特定问题或执行特定任务的明确定义的步骤或指令。
一般认为算法有以下五个特性:
- 确定性: 算法的每个步骤必须明确定义,没有歧义。
- 可行性: 算法在合理的时间和资源限制下能够被有效地执行。
- 有穷性: 算法必须在有限的步骤内完成,不会无限循环或永远执行下去。
- 输入项: 算法可以接受零个或多个输入。
- 输出项: 算法应当产生一个或多个输出。
算法的时间复杂度与空间复杂度
算法的时间复杂度/空间复杂度是用来衡量算法执行时间和空间资源消耗的度量指标。通常用大O符号表示,算法的时间/空间复杂度越低,资源的利用效率越高。
一般认为在1秒内计算机能够完成 10^8 次运算,实际通常会少一些,大约在 3~5*10^7 之间。想要在1s内完成运算,n的数量级必须在以下范围以内。
时间复杂度 | O(n) | O(nlogn) | O(n^2) | O(n^3) | O(2^n) | O(n!) |
---|---|---|---|---|---|---|
n的数量级 | <1x10^8 | <3x10^5 | <5x10^3 | <5x10^2 | <25 | <15 |
以下代码可以使用ctime来测量算法执行所花费的时间
clock_t st, ed;
st = clock();
// 算法在这里跑
ed = clock();
cout << (double)(ed-st)/CLOCKS_PER_SEC*1000 << "ms" << endl;
设计算法的流程
- 读题,理解题意
- 构思算法
- 验证是否可行,时间/空间复杂度是否达标
- 写出算法
- 找/修bug
使用对拍程序验证算法
对拍:将已知正确的算法与待验证的算法的输出相比较
通常已知正确的程序的时间复杂度不达标,是暴力解法
对拍程序的缺点:
- 需要花时间写暴力解
- 需要花时间出合法数据
//windows对拍程序示例代码
#include <bits/stdc++.h>
using namespace std;
int main(){
while (true){
system("待验证的程序.exe < 数据.in > 待验证的输出.out");
system("已知正确的程序.exe < 数据.in > 正确的输出.out");
//非0的返回值代表有差异
if (system("fc 待验证的输出.out 正确的输出.out"))
system("pause");
}
}
生成正负数随机数的方法
int seed = rand()%2;
int x = (rand()%range);
if (seed) x*=-1;
快读
是一种卡常技巧,当读入数据量大时有奇效
cin 是读入中最慢的,因为有同步流
可以通过在程序开始时添加一下代码关闭同步流
iOS::sync_with_stdio(0);
cin.tie(0);
读入速度:cin > scanf > 关闭同步流的cin > getchar快读
以下是快读int的代码
inline int read(){
int x=0, f=1; char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-')f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=x*10+ch-'0'; ch=getchar();
}
return x*f
}
枚举/暴力算法
枚举通过遍历所有的可能来解决问题
枚举三要素分别是枚举对象,范围,判定条件
三种常用的枚举方法是:
- 循环枚举
- 搜索枚举
- 二进制枚举(数字的每一位代表它的状态 1或0)
// 二进制枚举模板
for (int i=0; i<(1<<n); i++){
for (int j=0; j<n; j++){
if ((1<<j)&i){}
else {}
}
}
中途相遇法
一种枚举技巧,将数据分成两部分分别枚举,可以极大的优化二进制枚举
一般二进制枚举的时间复杂度为2^n, 优化后能达到2^(n/2)
n的数据量从24可以增加到48
典型例题:<a href="https://www.luogu.com.cn/problem/B3624">B3624</a>
全部评论 3
MD格式有些问题,记得改改
2024-05-22 来自 广东
1《O(!n)》
2024-05-20 来自 广东
1感谢指正
2024-05-23 来自 广东
0
久别重逢
2024-05-20 来自 新加坡
0好久不见啊
2024-05-23 来自 广东
0
有帮助,赞一个