Question

matlab 降低算法时间复杂度的方法？

第一次来知乎求教大神们！恳请多多指教！！我在用matlab编写一个小算法，这个算法里面可能多次循环的嵌套，导致得到最终结果（输入Reader=800,Tag=1000，r=30，范围为[1,900]的时候），花费了将近800多秒！！！劳驾各方神圣给我指点迷津，降低我这个算法的时间复杂度，有什么好点子好方法么？

更新：原题是RFID网络冗余阅读器去除算法，即要去除掉系统网络中冗余的阅读器，就是图中的红色圈圈，下图是已经去除后的效果。

【算法执行结果图如下】

算法设计：
① definition:
cc(covered count) ——每个tag被reader覆盖的数量（黑点到红圈圆心的距离：D<=r）
nc(neighbor count)——每个reader邻居的数量（两个圆圈原点距离：L<=2*r）
ncc(neighbor cover count)——每个reader的邻居所覆盖的所有tag数量的总和

② steps:
a.找出所有cc=1的tag，由于这些tag只被独有的reader覆盖，所以这些对应的reader为非冗余reader，其下所覆盖的所有tag均被该reader锁定(hold)；
b.当所有cc=1对应的reader被找到后，即剩下的tag的cc均>1，剩下的reader根据nc值由低到高依次循环执行c,d,e操作（邻居越多的阅读器在实际中越容易对其他阅读器产生干扰）；
c.当有多个nc值相等的reader，判断相同nc值的reader的ncc值大小，根据ncc的值由高到低循环进行d,e操作；
d.该reader中所有的tag的cc值减1，该reader为冗余reader；
e.找出c操作中cc=1的tag，重复a操作，假如依旧没有cc=1的tag，重复b操作；
f.直到所有tag均被reader锁定后，去除结束。

【附代码：】

%x1,y1,x2,y2是随机数，在其他函数里产生的已知变量，Reader, Tag, r均为GUI上输入的变量，输出为冗余阅读器数量和整个算法执行的时间
function [tcba_redundant,TCBAtime]=TCBA(x1,y1,x2,y2,Reader,Tag,r) 
%TCBA算法：
tic;
%%%%%%%%%%%%%【计算tagcc的值】%%%%%%%%%%%%%%%%
tagcc=zeros(1,Tag);
for j=1:Reader
    for i=1:Tag
        if showdistance(x1(j),y1(j),x2(i),y2(i))<=r 
            tagcc(i)=tagcc(i)+1;
% disp(strcat('tagcc: ',num2str(tagcc)));
%%%%%%%%%%%%%%%%%%%%%【找出cc=1的tag对应的reader（判断reader是否冗余），对于非冗余的reader所覆盖的tag进行锁定】%%%%%%%%%%%%%%%%%%%%%%
tagholder=zeros(1,Tag);
readerclosed=zeros(1,Reader);
readerredundant=ones(1,Reader);
for j=1:Reader
    for i=1:Tag
        if showdistance(x1(j),y1(j),x2(i),y2(i))<=r && tagcc(i)==1 && tagholder(i)==0
            tagholder(i)=j;
            for k=1:Tag
                if showdistance(x1(j),y1(j),x2(k),y2(k))<=r && tagholder(k)==0
                    tagholder(k)=j;
            readerclosed(j)=1;
            readerredundant(j)=0;
% disp(strcat('tagholder: ',num2str(tagholder)));
% disp(strcat('readerclosed： ',num2str(readerclosed)));
% disp(strcat('readerredundant： ',num2str(readerredundant)));
%%%%%%%%%%%%%【NC】%%%%%%%%%%%%%%%%
for a=1:Reader
    reader.nc(a)=0;
    reader.ncc(a)=0;
    for b=1:Reader
        if showdistance(x1(a),y1(a),x1(b),y1(b))<=2*r && showdistance(x1(a),y1(a),x1(b),y1(b))>0 &&readerclosed(a)==0 && readerredundant(a)==1
            reader.nc(a)=reader.nc(a)+1;
            %%%%%%%%%%%%%【NCC】%%%%%%%%%%%%%%%%
            for i=1:Tag
                if showdistance(x1(b),y1(b),x2(i),y2(i))<=r
                    reader.ncc(a)=reader.ncc(a)+1;
% disp(strcat('reader.nc: ',num2str(reader.nc)));
% disp(strcat('reader.ncc: ',num2str(reader.ncc)));
%%%%%%%%%%%%%【对于冗余的reader进行操作】%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%【根据reader的nc和ncc值由高到低进行筛选】%%%%%%%%%%%%%%%%
while (length(find(reader.nc==0))~=Reader)
    reader.ncmax=find(reader.nc==max(reader.nc));
    reader.ncc2=reader.ncc




    
(reader.ncmax);
    reader.nccmax=reader.ncmax(find(reader.ncc2==max(reader.ncc2)));
    ncc=reader.nccmax(1);
%     disp(strcat('reader.ncmax对应rid: ',num2str(reader.ncmax)));
%     disp(strcat('reader.ncmax对应ncc值(reader.ncc2): ',num2str(reader.ncc2)));
%     disp(strcat('reader.nccmax对应rid(ncc)，即要去除的reader为: ',num2str(ncc)));
    for k=1:Tag
        if showdistance(x1(ncc),y1(ncc),x2(k),y2(k))<=r
           tagcc(k)=tagcc(k)-1;
    reader.nc(ncc)=0;
    readerclosed(ncc)=1;
    %对剩下的reader重复最开始的操作进行判断是否为冗余reader
    for j=1:Reader
        if readerclosed(j)==0 && readerredundant(j)==1
            for i=1:Tag
                if showdistance(x1(j),y1(j),x2(i),y2(i))<=r && tagcc(i)==1 && tagholder(i)==0
                    tagholder(i)=j;
                    for h=1:Tag
                        if showdistance(x1(j),y1(j),x2(h),y2(h))<=r && tagholder(h)==0
                            tagholder(h)=j;
                    readerclosed(j)=1;
                    readerredundant(j)=0;
% disp(strcat('~tagcc: ',num2str(tagcc)));
% disp(strcat('~readerclosed： ',num2str(readerclosed)));
% disp(strcat('~readerredundant： ',num2str(readerredundant)));
% disp(strcat('~reader.nc: ',num2str(reader.nc)));
% disp(strcat('~reader.ncc: ',num2str(reader.ncc)));
% disp(strcat('~tagholder: ',num2str(tagholder)));
%%%%%%%%%%%%%%%%%%%%%【去除没有hold任何标签的reader】%%%%%%%%%%%%%%%%%%%%%%
a=unique(tagholder);
holderid=a(find(a~=0));
disp(strcat('覆盖有标签的reader的rid为：',num2str(holderid)));
cla(gca);
for k=holderid
        sita=0:pi/20:2*pi;%角度[0,2*pi]
        xr=x1(k)+r*cos(sita);
        yr=y1(k)+r*sin(sita);
        readers=plot(xr,yr,'-r');
        hold on;
%对坐标轴进行相关设置    
[tags,TO,tid]=tag(x2,y2,Tag);
h=legend([readers,tags],'reader','tag');
set(h,'color',[1 1 0]);
%%%%%%%%%%%%%【计算冗余的reader数量】%%%%%%%%%%%%%%%%
tcba_redundant=Reader-length(holderid);
fprintf('TCBA算法得到冗余阅读器个数：%d\n',tcba_redundant);
%%%%%%%%%%%%%%%%%%%%%【TCBA算法执行所需时间】%%%%%%%%%%%%%%%%%%%%%%
time=toc;
TCBAtime=num2str(time);
fprintf('TCBA算法执行所需时间为：%s秒\n',TCBAtime);
fprintf('------------------------------------------------\n');

代码写的不漂亮望大神们见谅！！

------------华丽的分割线----------（根据知友@小耿的帮助进行修改结果图）---------------↓ ↓ ↓ ↓ ↓ ↓ ↓

【具体修改代码见下面我的回答】

4 个回答

小耿 生物狗转职程序猿 · Accepted Answer

（如果大神来答过就不会有人看我的答案了。所以我要赶在大神之前把答案发出来，这样就会有人看了来指正，这样我就会进步。

以上是我的小心思，恩。）

首先抱歉，我不熟悉matlab。以下不能保证语法都正确。

题主你代码的主要问题在于执行了太多次showdistance()函数。我一块一块说。

假设reader数是m，tag数是n。

一，计算tagcc部分

如果是我的话，我会用一个n*m的矩阵（比如A = zeros[n,m]）把每一个reader是否覆盖某一个tag保存起来（如果覆盖，就将矩阵中对应的值设为1）。这样，我之后再也无需调用showdistance()函数来寻找reader覆盖的tag，而是直接从矩阵中读取结果：

首先，第j个reader是否覆盖第i个tag就只要看是否A(i,j)>0；

其次，第i个tag的CC值是sum(A(i,:))，第j个reader覆盖量为sum(A(:,j))；

第三，覆盖第i个tag的reader为find(A(i,:)>0)，第j个reader覆盖的tag是find(A(:,j)>0)。

全部转化为了矩阵操作，不仅减少了循环次数而且效率高，空间换取时间。

二，判断reader是否冗余部分

上面的矩阵就派上用场了：

for j=1:Reader
    for i = find(A(:,j)>0)
        if tagcc(i) == 0
            %别忘了先把不覆盖任何tag的reader去掉
        elseif tagcc(i) == 1
            %锁定非冗余reader
...

三，计算reader.nc部分

第43行：

for b=1:Reader

这里没必要从1开始循环，可以从a+1开始。但要注意修改：

1，除了reader.nc(a)，reader.nc(b)也要+1。

2，第44行无需showdistance(x1(a),y1(a),x1(b),y1(b))>0这个判断条件了。

另外第44行可以把readerclosed(a)==0这个条件放在showdistance(x1(a),y1(a),x1(b),y1(b))<=2*r前面。这样当前者为假时，可以短路跳过后者，减少showdistance()执行次数。

四，算法部分

后半部分判断冗余reader和前面一样可以优化。我是想说一下前半部分“寻找nc最大值的reader中ncc最大值的那个”。这部分寻找一次的复杂度是O(m)，加上外层while循环就是O(m^2)。

我不太熟悉matlab。如果是别的语言，我会用priority queue，这样复杂度可以降到O(m·logm)。

你需要两个priority queue，第一个出队nc最大值（可以叫ncPq），第二个出队ncc最大值（可以叫nccPq）。我写个伪代码：

所有未锁定reader加入ncPq
while nccPq或ncPq非空
    if nccPq为空
        ncPq最大值出队，加入nccPq