算法复习笔记(二)蛮力法
蛮力法的主要应用于遍历部分。遍历数组,遍历集合,遍历二叉树
1.下面我们主要讲解一下查找问题中的蛮力法
虽然低效,但是对于查找集合不大的情况下是一种合理的方法
1.1 顺序查找:在数组r[1] ~r[n]查找元素k
int SeqSearch1(int r[],int n,int k)
{
int i=n;
while(i>0 &&r[i]!=k)
i--;
return i;
}
算法分析:基本语句时判定条件,其平均执行次数为o(n);
1.2 将待查找的数放在尽头,免去每次是否判断越界
int SeqSearch1(int r[],int n,int k)
{
int i=n;
r[0]=k;
while(r[i]!=k)
i--;
return i;
}
虽然数量级相同,但是系数相差一半
2.串匹配问题
BF(朴素模式匹配算法):
核心:在不想等,则从主串s的第二个字符开始和第一个字符进行比较
int BF(char S[],char T[])
{
int index=0;
int i=0,j=0;
while(S[i]!='\0' && T[j]!='\0')
{
if(S[i]==T[j])
{
i++;
j++;
}
else
{
index++;i=index;j=0;
}
}
if(T[j]!='\0')
return index+1;
else
return 0;
}
分析:
设匹配成功发生在si处,则在前i-1趟不成功匹配中比较了(i-1)*m次,一共比较i*m次,前面m此都匹配成功,求其平均匹配次数,每一次的概率想等,求和,则有:
m*(n-m+2)/2 (Ps:求解过程这里就不列出来了 有问题的欢迎留言)
一般情况下,m<<n,因此在最坏的情况下其时间复杂度O(n*m)
2.2kmp算法:
记:文本长度为N,模式串长度为M
BF算法的时间复杂度O(N*M),空间复杂度O(1)
KMP算法的时间复杂度O(M+n) 空间复杂度O(N)
kmp关键的地方是求模式串的next数值:
毕竟学了数据结构当时这里就没有卡多久,但是分析的时候坑爹的地方还是挺多的:
求解next的定义不同就导致,next 填表不同,虽然算法的执行是没有影响的 但这却会照成阅读障碍
我们先对j=0的next 赋予-1,模式串从0数开始,不想等
比如:
模式串: a b a a b c a b a
next: -1 0 0 1 1 2 0 1 2
具体的求解方法,请看博文https://blog.csdn.net/qq_37457202/article/details/80449164
下一章对其进行了详细的分析,这里就不做过多的叙述了
附上代码
void Calenext(char *p,int next[])
{
int nLen=strlen(p);
next[0]=-1;
int k=-1;
int j=0;
while(j<nLEN-1)
{
if(K==-1 ||P[j]==P[k])
{
++k;
++j;
next[j]=k;
}
else
{
k=next[k];
}
}
}
3.蛮力法排序
选择排序:时间复杂度(O(n的平方))
起泡排序:重点。⚠️⚠️⚠️
4.组合问题中的蛮力法
QAQ临时有事 今天补上
相关文章
- 无意中发现一位大佬的算法刷题 pdf 笔记
- 算法(第四版)学习笔记之java实现希尔排序
- 带花树算法学习笔记
- 【算法】【递归与动态规划模块】判断字符串的顺序交错组成
- 字符串匹配算法之KMP&Boyer-Moore
- 基于GA优化BP神经网络的传感器故障诊断算法matlab仿真
- 【神经网络避障】基于BP神经网络的小车行驶避障算法仿真
- C#,码海拾贝(09)——阿克玛(Akima)曲线光滑插值算法,《C#数值计算算法编程》源代码升级改进版
- 简易的算法板子
- 机器学习笔记之决策树算法(一)基本介绍
- 机器学习笔记之高斯混合模型(三)EM算法求解高斯混合模型(E步操作)
- 《模式识别》学习笔记(十二)一般情况下判别函数权矢量算法
- 《模式识别》学习笔记(六)聚类算法之简单聚类算法和谱系聚类算法
- 《数据挖掘:理论与算法》学习笔记(六)—神经网络
- 十大经典排序算法【算法思想+图解+代码】【数据结构与算法笔记】
- 《数据结构与算法 C语言版》—— 2.4典型例题
- 最短路径:Dijstra(迪杰斯特拉)算法
- 算法复习笔记(四)减治法
- 算法复习笔记之重要算法(二)
- 一致性哈希算法的领悟
- 【算法/回溯算法/棋盘问题】题解+详细备注(共2题)
- 华为OD机试 - 投篮大赛(JavaScript) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 最小施肥机能效(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 逆向解读割木板问题贪心算法合理性
- 算法积累:解决如何获取指定文件夹路径或者文件路径下所有子文件后缀为.h .m .c的文本的行数
- 人工智能算法模型--Alpha-Beta剪枝算法学习笔记
- python算法之组合总和