XP02
2026-07-14 21:33:26
发布于:浙江
Day01
时间复杂度
概念:可用来衡量程序或算法执行效率或速度
时间频度
一个算法中的语句执行次数成为语句频度或时间频度,记为 ,在代码中我们通常会计算每一行语句的执行次数相加得到 。
大 O 表示法
最坏时间复杂度
时间复杂度越高,效率越慢。
C++ 程序 秒执行次数在 左右。
简化规则:
- 代表所有常数时间复杂度
比如: - 修改后的时间频度函数 ,只保留最高阶
比如: - 若最高阶系数存在且不是 ,则删去该常数
比如:
常数阶 线性阶 平方阶 对数阶
数学
可以知道 ,读作 以 为底 的对数等于 。

枚举算法
枚举算法是一种将问题的所有可能结果一一列举,并用条件检验是否成立的解题思维。
- 枚举数字
- 枚举数组元素(数字 变成 对应下标)
枚举思路:
- 确定枚举对象有几个,对应 for 循环嵌套个数。
- 确定每个枚举对象的范围。
- 编写判断条件(易错点在优化后会忘记调整)。
- 如果枚举出现 TLE 了,那么我们需要进行优化,优化后一定要去确保计算出来的值在范围内。
模拟算法
问题怎么描述,程序步骤就怎么设计。
额外知识点
平方数判断
int k = sqrt(N);
if(k * k == N){
N 是平方数
}
约数个数
int cnt = 0;
for(int i = 1; i * i <= N; i ++ ){
if(n % i == 0){
if(n / i != i) cnt ++ ;
cnt ++ ;
}
}
Day03
二分查找步骤
-
确定查找范围,
-
范围存在,
eg: ,找不到任何一个元素既大于等于 5 又小于等于 4。 -
只要范围存在,找中间的一个元素,
int mid = (left + right) / 2;常用版本:
(left + right) / 2防止越界版本:
(right - left) / 2 + left -
分成三部分,根据比较结果去修改对应范围:
- 更小数:L 到 mid-1
- 自己:mid
- 更大数:mid+1 到 R
left: 最小
right: 最大
mid: 每次要猜的数字
while(left <= right){
int mid = (left + right) / 2;
if(x == arr[mid]){
ans = mid;
break;
}
else if(x < arr[mid]){
right = mid - 1; // 往左找
}
else{
left = mid + 1; // 往右找
}
}
大于等于 x 的第一个数下标
while(left <= right){
int mid = (left + right) / 2;
if(x <= arr[mid]){
ans = mid;
right = mid - 1;
}
else{
left = mid + 1; // 往右找
}
}
对应函数
lower_bound(数组名+开始下标, 数组名+结束下标+1, 查询元素) - 数组名
找到得到对应下标, 找不到结果为 结束下标+1
第一个大于 x 的第一个数下标
while(left <= right){
int mid = (left + right) / 2;
if(x < arr[mid]){
ans = mid;
right = mid - 1;
}
else{
left = mid + 1; // 往右找
}
}
对应函数
upper_bound(数组名+开始下标, 数组名+结束下标+1, 查询元素) - 数组名
找到得到对应下标, 找不到结果为 结束下标+1
元素出现个数 = upper_bound - lower_bound
全部评论 4
有Day4的吗?
2026-07-24 来自 浙江
2
2026-07-17 来自 广东
1d
2026-07-15 来自 浙江
11
2026-07-15 来自 浙江
1





























有帮助,赞一个