论坛 › 技巧探讨 › 为什么写循环时要把小循环作为外侧循环？

元始天尊 发表于 2014-7-19 22:10:25

为什么写循环时要把小循环作为外侧循环？

我们总是说，为了提高程序效率，再遇到多重循环时，应该吧小循环作为外侧循环而大循环作为内测循环，这个是为什么呢？
下面是个简单的矩阵加法例子：

Void Addm(T** a,...)
{
        for(int i=0;i<rows;i++)
                for(int j=0;j<cols;j++)
                        c=a+b;
       
}


语句s/e 频率 总步数
Void Addm(T** a,...)0 0 0
{ 0 0 0
for(int i=0;i<rows;i++) 1 rows+1 rows+1
    for(int j=0;j<cols;j++)1 rows*(cols+1) rows*cols+rows
      c=a+b1 rows*cols rows*cols
} 0 0 0
总计 2*rows*cols+2*rows+1


(以下++、赋值、判断均看做单位时间操作)
for(int i=0;i<rows;i++)       
这一句从i=0 i=1 ... 直到i=rows判断出界才终止，因此对i的操作次数为rows+1次
for(int j=0;j<cols;j++)
这一句由于上面i的循环体实际循环了rows次，而j的操作次数类似于上一句为cols+1次，因此总共为rows*(cols+1)次
循环体中循环次数由上面可以看出来循环体循环了rows*cols次，因此c这句步数是rows*cols
和为：2*rows*cols+2*rows+1
因此当外循环次数较大，即rows远大于cols，其步数将会远大于将次数较多的循环放到内存的的步数，得证

元始天尊 发表于 2014-7-28 23:23:15

算法笔记-寻找第N小元素：
设数组大小为SIZE
如果N=SIZE/2 则为求中位数的问题，如果N=0或SIZE-1则为求最值问题

// findth.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[])
{
const int size=7;
int data;
for(int i=0;i<size;i++)
{
data=rand()&0xFF;
printf("%d\n",data);
}
printf("\n");

for(int tofindindex=0;tofindindex<size;tofindindex++)
{
int begin=0,end=size-1;

while(true)
{
   int tmp=data;
   int begin1=begin,end1=end;
   while(begin1 < end1)
   {
    while(begin1 < end1 && data >= tmp)
   end1--;
    data=data;
    while(begin1 < end1 && data <= tmp)
   begin1++;
    data=data;
   }
   data=tmp;
   
   if(tofindindex > begin1)
   {
    begin=begin1+1;
   }
   else if(tofindindex < begin1)
   {
    end=begin1-1;
   }
   else
   {
    printf("The %dth is %d\n",tofindindex,data);
    break;
   }
}
}

getchar();
}

// 41
// 35
// 190
// 132
// 225
// 108
// 214
//
// The 0th is 35
// The 1th is 41
// The 2th is 108
// The 3th is 132
// The 4th is 190
// The 5th is 214
// The 6th is 225





贪心算法：
procedure GREEDY(A,n)
    solution<-∅
    for i<-1 to n do
      x<-SELECT(A)
      if FEASIBLE(solution,x)
      then solutions<-UNION(solution,x)
      endif
    repeat
    return(solution)
end GREEDY

选择能产生问题最优解的最有亮度标准是使用贪心发设计求解的核心问题

背包问题：
    p1/w1>=p2/w2>=...>=pn/wn
procedure KNAPSACK(P,W,M,X,n)
    P(i)/W(i)>=P(i+1)/W(i+1)
    real P(1:n),W(1:n),X(1:n),M,cu;
    integer i,n;
    X<-0
    cu<-M
    for i<-1 to n do
      if W(i)>cu then exit endif
      X(i)<-1
      cu<-cu-W(i)
    repeat
    if i<=n then X(i)<-cu/W(i)
    endif
end KNAPSACK




分治法：

二分检索算法：A有序
procedure BINSRCH(A,n,x,j)
//查找x，如果找到则用j设置
    integer low,high,mid,j,n;
    low<-1;high<-n
    while low<=high do
      mid<-/2
      case
             x<A(mid):high<-mid-1
             x>A(mid):low<-mid+1
   else:j<-mid:return
endcase
    repeat
    j<-0
end BINSRCH

找最大和最小元素
procedure MAXMIN(i,j,fmax,fmin)
//fmax fmin存放最大和最小元素
    integer i,j;global n,A(1:n)
    case
      i=j:fmax<-fmin<-A(i)//只有一个元素
      i=j-1;if A(i)<A(j) then fmax<-A(j);fmin<-A(i)//有2个元素
               else fmax<-A(i);fmin<-A(j)
               endif
      else
            mid<-/2
            call MAXMIN(i,mid,max1,min1)
            call MAXMIN(mid+1,j,max2,min2)
            fmax<-max(max1,max2)
            fmin<-min(min1,min2)
    endcase
end MAXMIN

复杂度：
T(0)=0
T(1)=1
T(n)=2*T(n/2)+2=3n/2-2 好于直接比较的2n-2

归并排序：
procedure MERGESORT(low,high)
    integer low,high;
    if low<high then
      mid<-n/2
      call MERGESORT(low,mid)
      call MERGESORT(mid+1,high)
      call MERGE(low,mid,high)
    endif
end MERGESORT

procedure MERGE(low,mid,high)
    integer h,i,j,k;
    h<-low;i<-low;j<-mid+1
    while h<=mid and j<=high do
      if A(h)<=A(j) then B(i)<-A(h);h<-h+1
      else B(i)<-A(j);j<-j+1
      endif
      i<-i+1
    repeat
    if h>mid then
      for k<-j to high do
            B(i)<-A(k);i<-i+1
      repeat
    else
      for k<-h to mid do
            B(i)<-A(k);i<-i+1
      repeat
    endif
end MERGE

      复杂度：
      T(1)=a
      T(n)=2T(n/2)+cn=2^k*T(1)+kcn;=O(nlogn)

快速排序：
    快速分类：吧小于某元素和大于某元素的元素移动到2边
procedure QuickSort(p,q)
    int p,q;global n,A
    if p<q then
      j=q+1;Partition(p,j)
      QuickSort(p,j-1);
      QuickSort(j+1,q);
    endif
end QuickSort

procedure PARTITION(m,p)
    integer m,p,i;global A(m:p-1)
    v<-A(m);i<-m
    loop
      loop i<-i+1 until A(i)>=v repeat
      loop p<-p-1 until A(p)<=v repeat
      if i<p
            then call INTERCHANGE(A(i),A(p))
            else exit
      endif
    repeat
    A(m)<-A(P)
End PARTITION

      复杂度：
      最坏情况下O(n^2)，平均O(nlogn)




满二叉树：
    深度为k且有2^k-1个节点的二叉树称为满二叉树。
    编号从根节点起，自上而下自左向右。
完全二叉树：
    深度为k且有n个节点的二叉树，当且仅当每一个节点都与深度为k的满二叉树中编号从1至n的节点一一对应的二叉树称为完全二叉树

    节点个数=分支个数+1
    所有节点度之和=2*边数

多项式合并：
多项式合并代码：
// test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <stdio.h>
#include <malloc.h>

struct ElemType
{
ElemType* next;
float coef;//系数
int expn;//指数
};

ElemType* head1=NULL;
ElemType* head2=NULL;

ElemType* CreatePolyn()
{//初始化多项式
ElemType* head=(ElemType*)malloc(sizeof(ElemType));
head->next=NULL;
return head;
}

void AddPolyn(ElemType* head,float coef,int expn)
{//增加多项式节点
if(coef == 0.0)
return;
for(ElemType* cur=head;cur->next != NULL && cur->next->expn < expn;cur=cur->next);
ElemType* newnode=(ElemType*)malloc(sizeof(ElemType));
newnode->next=cur->next;
newnode->coef=coef;
newnode->expn=expn;
cur->next=newnode;
}

void PrintPolyn(ElemType* head)
{//打印多项式
for(ElemType* cur=head->next;cur != NULL;cur=cur->next)
{
printf("coef:%f,expn=%d\n",cur->coef,cur->expn);
}
}

void MergePolyn(ElemType* head1,ElemType* head2)
{//合并多项式head1+head2->head1
ElemType* cur1=head1;

while(cur1->next && head2->next)
{
ElemType* cur2=head2->next;

if(cur2->expn < cur1->next->expn)//插入cur1之前
{
   head2->next=cur2->next;
   cur2->next=cur1->next;
   cur1->next=cur2;
}
else if(cur2->expn == cur1->next->expn)
{
   cur1->next->coef += cur2->coef;
   
   if(cur1->next->coef == 0)
   {
    ElemType* p=cur1->next;
    cur1->next=p->next;
    delete p;
   }
   else
   {
    cur1=cur1->next;
   }
   head2->next=cur2->next;
   delete cur2;
}
else
{
   cur1=cur1->next;
}

}

if(head2->next)
cur1->next=head2->next;
head2->next=NULL;
}

void DestroyPolyn(ElemType* head)
{//销毁多项式
ElemType* cur=head;
while(cur->next)
{
ElemType* p=cur->next;
delete cur;
cur=p;
}
}

int main(int argc, char* argv[])
{
head1=CreatePolyn();
head2=CreatePolyn();
//7+3x+9x^8+5x^17
AddPolyn(head1,7,0);
AddPolyn(head1,3,1);
AddPolyn(head1,9,8);
AddPolyn(head1,5,17);
printf("head1:\n");
PrintPolyn(head1);

//8x+22x^7-9x^8
AddPolyn(head2,8,1);
AddPolyn(head2,22,7);
AddPolyn(head2,-9,8);
printf("head2:\n");
PrintPolyn(head2);

MergePolyn(head1,head2);
printf("head1:\n");
PrintPolyn(head1);
printf("head2:\n");
PrintPolyn(head2);
DestroyPolyn(head1);
DestroyPolyn(head2);

getchar();
return 0;
}




单链表头结点移动到链表最后：
    Status A(LinList L)
    {
      if(L && L->next)   
      {
            Q=L;
            L=L->next;
            P=L;
            while(P->next) P=P->next;
            P->next=Q;
            Q->next=NULL;
      }
      return OK;
    }

双链表拆分成2个双链表
    void BB(LNode* s,LNode* q)
    {
      p=s;
      while(p->next != q)
            p=p->next;
      p->next=s;
    }

    void AA(LNode* pa,LNode* pb)
    {
      BB(pa,pb);
      BB(pb,pa);
    }

10进制转换为8进制
    void conversion()
    {
      InitStack(S);
      scanf("%d",N);
      while(N)
      {
            Push(S,N%8);
            N=N/8;
      }
      while(!StackEmpty(s))
      {
            Pop(S,e);
            printf("%d",e);
      }
    }

查看完整版本: 为什么写循环时要把小循环作为外侧循环？