算法分析的目的是分析算法的,找众数算法的方法,算法分析的目的是分析算法的,找众数算法的关系
版权声明:本文由科林蔡原创。欢迎投稿。粘贴必须指示原始文本的URL。
www.cn blogs.com/Colin-Cai/p/12664044.html街33558号
作者:视窗
QQ/微信:6679072
电子邮件:6679072@qq.com
众数是长度len的排列,出现次数比len/2多,来源于如何求这个数的话题。
基于排序
排序是第一感觉。对这个数组进行排序,并再次遍历它以获得结果。
如果用C语言写,基本如下。
intfind(inta,int len)).
{
sort(a,len);
遍历(a,len);
}
有时间复杂度为o (nlogn)的算法,如快速排序、归并排序、堆排序,但遍历排序后数组的结果是时间线性复杂度,即o(n)。因此,整个算法的时间复杂度为o(nlogn)。
寻找更好的算法
上面的算法很简单。很多时候,我们第一感觉到的不一定可靠。
能否找到线性时间层次的算法,即(n)时间层次的算法?它是一个上下边界相同的符号。其实很容易证明,不存在低于线性时间层次的算法,即时间o(n)。小O不同于大O,指向无穷的低层次。证据大致如下
如果算法能以o(n)的时间复杂度解决上述问题。因为它的无穷大小于N,所以一定有一个长度为N的数组,算法完成后,数组中检测到的元素小于N/2。将算法运算的结果设置为A,然后,数组会用相同的数字B代替算法得到的结果A,替换算法运算时没有检测到的所有元素。然后,通过算法操作新的数组。未检测到的量不会影响算法的结果,所以结果还是a .但实际上数列出现N/2次以上的次数是b .所以因为矛盾,所以这个问题没有o(n)时间算法。
现在我们可以开始思考更深层的东西了。
首先,如果一个数组中有两个不同的数字,将这两个数字从数组中去掉,得到一个新的数组。您会发现新阵列仍然具有与旧阵列相同的模式。这很容易证明:
假设数组为A,长度为len,模式数为X,出现次数为T,当然满足tlen/2。假设里面有两个Y和Z。yz .除了这两个数,剩下的数组长度是len-2。如果两个模式X,即xy和xz不相等,那么T仍然是新数组的模式号,因为X在新数组中的出现次数仍然是T,tlen/2(len-2 )/2。另一方面,当这两个数中有X时,当然只有一个X,所以X在其余排列中出现的次数是t-1,t-1len/2-1=(len-2 )/2,所以X仍然是新排列中出现频率最高的值。
如果我有上面的想法,我会考虑如何求这一对的不同数。
您可以记录数值num及其重复次数,遍历数组,并根据下面的流程图进行操作。
Num/times记录数字及其重复次数。乘以加1和减1取决于数组的新数字是否与num相同。如果减去1,就要看实际证明的命题了。找出不同的数字对。删除这两个后,剩余数组的模式号保持不变。
就是证明最后的结果是需要的模式。如果后续的结果不是最频繁的值,那么每次最频繁的值出现时,都会用非频繁值的个数“抵消”,所以数组中非频繁值的个数不会少于最频繁值的个数。然而,这并不是现实。因此建立上述算法,线性时间复杂度o(n),常数空间复杂度o) )1)。
c语言代码基本如下。
intfind(int*a,int len)).
{
int i,num=0,times=0;for(I=0;我
如果(时间0) {
if(num==a[I]).
时间;
其他
次-;
}否则{
num=a[I];
时间=1;
}
}
退货数量;
}
使用程序时,程序简化如下。
(定义(查找))
(汽车)
(向右折叠)
((NR))
(如果)零?(cdr r)
(反对意见1)
(cons(carr ) ) ) if ) eq?n(carr ) ) ) ) (cdr )1))
()))). 0 ) s))
升级后的问题
上面的模式数超过了数组长度的1/2。把这里的1/2换成1/3怎么办?
例如,如果数组是[1,1,2,3,4],找到的模式数是1。
我们来升华一下。如果是1/m,这里m是一个参数。我怎样才能找到它?这个问题,走之前,那个问题
有些很复杂。另外要意识到,问题升级后,可能不止一种模式。例如,[1,1,2,2,3]的长度为5,1和2都大于5/3。最多有m-1个模式。
思考
如果还是先排序再遍历,还是有效的,但是时间复杂度还是O(nlogn)级,所以还是期待线性时间复杂度的算法。
对于第一个问题,前提是去掉数组中两个不同的数,模式不变。那么升级后的问题还有类似的结果吗?与之前不同的是,我们来看看当模式从大于1/2变为大于1/m时会发生什么,我们来看看长度为len的数组A中M个不同数的去除。认证过程如下:
同样,我们假设A中有一个模X,X的出现次数为t,我们看看去掉M个不同的数后X是否还是那个模。去掉M的个数后,新数组的长度是len-m. X是众数,所以X的出现次数是t len/m .如果去掉的M个数中没有X,剩下的数组中X的出现次数仍然是t,t len/m (len-m)/m,所以在这种情况下,X仍然是众数;如果去掉的M个数中有X,由于M的个数互不相同,所以只有一个X,所以剩余数组中X的出现次数为t-1,t len/m,所以t-1 len/m-1=(len-m)/m,所以剩余数组中X仍然占多数。这适用于上述阵列中的所有模式。类似地,对于数组中不是众数的数字,剩余的数组仍然不是众数。其实以上都用代替就够了
有了以上的理解,我们就可以按照前面的算法,只是这里改成了最大长度为n-1的链表。例如,对于数组[1,2,1,3],模式1超过数组长度4的1/3,过程如下
初始空链表[]
检索第一个元素1,发现链表中没有num=1的元素,链表的长度也没有达到2,所以将其插入链表,得到[(num=1,times=1)]
检索第二个元素2,发现链表中没有num=2的表元素,链表长度没有达到2。将其插入到链表中得到[(num=1,times=1),(num=2,times=1)]
搜索第三个元素1,发现链表中已经有一个num=1的元素,然后在元素times上加1得到[(num=1,times=2),(num=2,times=1)]
检索第四个元素3,发现链表中没有num=3的元素,链表的长度已经达到最大,等于2。于是,进行消除,即每个元素的次数减1,减为0的元素从链表中删除,得到[(num=1,times=1)]
这就是上面的过程,最后的结果是模式为1。
以上过程最终得到的链表确实包含了所有的模式,这个很容易证明,因为任何模式的次数都不可能完全取消。然而,上述过程实际上并不能保证所有的模式都在最终的链表中。比如[1,1,2,3,4]最后得到[(num=1,times=1),(num=4,times=1)],但4不是众数。
所以在我们得到这个链表之后,我们需要再次遍历数组,记录链表中的重复次数。
Python使用map/reduce高阶函数代替过程式下的循环,上面的算法也需要如下这么多代码。
从functools导入减少
定义查找(a,m):
定义find_index(arr,test):
对于范围内的I(len(arr)):
if测试(arr[i]):
返回I
返回-1
定义检查(r,n):
index=find_index(r,x:x[0]==n)
如果索引=0:
r[索引][1]=1
返回r
如果len(r) m-1:
return r [[n,1]]
return reduce(lambda arr,x : arr if x[1]==1 else arr [[x[0],x[1]-1]],r,[])
定义计数(r,n):
index=find_index(r,x:x[0]==n)
如果索引为0:
返回r
r[索引][1]=1
返回r
如果x[1]len(a)//m else r,\
减少(计数,a,\
list(map(lambda x : [x[0],0],reduce(check,a,[]))),[])
如果用C语言写代码会更多,但是可以用定长数组代替链表,效率会高很多。times=0表示元素未被占用。在这里不会实现。让感兴趣的读者自己体会吧。
关于查找教程网络
本站仅代表作者观点,不代表本站立场。所有文章均免费分享,不以盈利为目的。
该网站提供软件编程、网站开发技术、服务器运维、人工智能等IT技术文章。希望程序员好好学习,让我们用科技改变世界。
【模式的算法分析】http://www.zyiz.net/tech/detail-126392.html
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。