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

元始天尊

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

1. 
   
2. Void Addm(T** a,...)
   
3. {
   
4.         for(int i=0;i<rows;i++)
   
5.                 for(int j=0;j<cols;j++)
   
6.                         c[i][j]=a[i][j]+b[i][j];
   
7.        
   
8. }

复制代码

语句	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[i ][j]=a[i ][j]+b[i ][j]	1	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[i ][j]这句步数是rows*cols
和为：2*rows*cols+2*rows+1
因此当外循环次数较大，即rows远大于cols，其步数将会远大于将次数较多的循环放到内存的的步数，得证

元始天尊

算法笔记-寻找第N小元素：

1. 设数组大小为SIZE
   
2. 如果N=SIZE/2 则为求中位数的问题，如果N=0或SIZE-1则为求最值问题
   
3. 
   
4. // findth.cpp : Defines the entry point for the console application.
   
5. //
   
6. 
   
7. #include "stdafx.h"
   
8. #include <stdio.h>
   
9. #include <stdlib.h>
   
10. 
    
11. int main(int argc, char* argv[])
    
12. {
    
13. const int size=7;
    
14. int data[size];
    
15. for(int i=0;i<size;i++)
    
16. {
    
17.   data[i]=rand()&0xFF;
    
18.   printf("%d\n",data[i]);
    
19. }
    
20. printf("\n");
    
21. 
    
22. for(int tofindindex=0;tofindindex<size;tofindindex++)
    
23. {
    
24.   int begin=0,end=size-1;
    
25. 
    
26.   while(true)
    
27.   {
    
28.    int tmp=data[begin];
    
29.    int begin1=begin,end1=end;
    
30.    while(begin1 < end1)
    
31.    {
    
32.     while(begin1 < end1 && data[end1] >= tmp)
    
33.      end1--;
    
34.     data[begin1]=data[end1];
    
35.     while(begin1 < end1 && data[begin1] <= tmp)
    
36.      begin1++;
    
37.     data[end1]=data[begin1];
    
38.    }
    
39.    data[begin1]=tmp;
    
40.    
    
41.    if(tofindindex > begin1)
    
42.    {
    
43.     begin=begin1+1;
    
44.    }
    
45.    else if(tofindindex < begin1)
    
46.    {
    
47.     end=begin1-1;
    
48.    }
    
49.    else
    
50.    {
    
51.     printf("The %dth is %d\n",tofindindex,data[tofindindex]);
    
52.     break;
    
53.    }
    
54.   }
    
55. }
    
56. 
    
57. getchar();
    
58. }
    
59. 
    
60. // 41
    
61. // 35
    
62. // 190
    
63. // 132
    
64. // 225
    
65. // 108
    
66. // 214
    
67. //
    
68. // The 0th is 35
    
69. // The 1th is 41
    
70. // The 2th is 108
    
71. // The 3th is 132
    
72. // The 4th is 190
    
73. // The 5th is 214
    
74. // The 6th is 225

复制代码

贪心算法：

1. procedure GREEDY(A,n)
   
2.     solution<-∅
   
3.     for i<-1 to n do
   
4.         x<-SELECT(A)
   
5.         if FEASIBLE(solution,x)
   
6.         then solutions<-UNION(solution,x)
   
7.         endif
   
8.     repeat
   
9.     return(solution)
   
10. end GREEDY
    
11. 
    
12. 选择能产生问题最优解的最有亮度标准是使用贪心发设计求解的核心问题
    
13. 
    
14. 背包问题：
    
15.     p1/w1>=p2/w2>=...>=pn/wn
    
16. procedure KNAPSACK(P,W,M,X,n)
    
17.     P(i)/W(i)>=P(i+1)/W(i+1)
    
18.     real P(1:n),W(1:n),X(1:n),M,cu;
    
19.     integer i,n;
    
20.     X<-0
    
21.     cu<-M
    
22.     for i<-1 to n do
    
23.         if W(i)>cu then exit endif
    
24.         X(i)<-1
    
25.         cu<-cu-W(i)
    
26.     repeat
    
27.     if i<=n then X(i)<-cu/W(i)
    
28.     endif
    
29. end KNAPSACK
    
30. 
    

复制代码

分治法：

1. 二分检索算法：A[1:n]有序
   
2. procedure BINSRCH(A,n,x,j)
   
3. //查找x，如果找到则用j设置
   
4.     integer low,high,mid,j,n;
   
5.     low<-1;high<-n
   
6.     while low<=high do
   
7.         mid<-[low+high]/2
   
8.         case
   
9.              x<A(mid):high<-mid-1
   
10.              x>A(mid):low<-mid+1
    
11.    else:j<-mid:return
    
12. endcase
    
13.     repeat
    
14.     j<-0
    
15. end BINSRCH
    
16. 
    
17. 找最大和最小元素
    
18. procedure MAXMIN(i,j,fmax,fmin)
    
19. //fmax fmin存放最大和最小元素
    
20.     integer i,j;global n,A(1:n)
    
21.     case
    
22.         i=j:fmax<-fmin<-A(i)//只有一个元素
    
23.         i=j-1;if A(i)<A(j) then fmax<-A(j);fmin<-A(i)//有2个元素
    
24.                  else fmax<-A(i);fmin<-A(j)
    
25.                  endif
    
26.         else
    
27.             mid<-[i+j]/2
    
28.             call MAXMIN(i,mid,max1,min1)
    
29.             call MAXMIN(mid+1,j,max2,min2)
    
30.             fmax<-max(max1,max2)
    
31.             fmin<-min(min1,min2)
    
32.     endcase
    
33. end MAXMIN
    
34. 
    
35. 复杂度：
    
36. T(0)=0
    
37. T(1)=1
    
38. T(n)=2*T(n/2)+2=3n/2-2 好于直接比较的2n-2
    
39. 
    
40. 归并排序：
    
41. procedure MERGESORT(low,high)
    
42.     integer low,high;
    
43.     if low<high then
    
44.         mid<-n/2
    
45.         call MERGESORT(low,mid)
    
46.         call MERGESORT(mid+1,high)
    
47.         call MERGE(low,mid,high)
    
48.     endif
    
49. end MERGESORT
    
50. 
    
51. procedure MERGE(low,mid,high)
    
52.     integer h,i,j,k;
    
53.     h<-low;i<-low;j<-mid+1
    
54.     while h<=mid and j<=high do
    
55.         if A(h)<=A(j) then B(i)<-A(h);h<-h+1
    
56.         else B(i)<-A(j);j<-j+1
    
57.         endif
    
58.         i<-i+1
    
59.     repeat
    
60.     if h>mid then
    
61.         for k<-j to high do
    
62.             B(i)<-A(k);i<-i+1
    
63.         repeat
    
64.     else
    
65.         for k<-h to mid do
    
66.             B(i)<-A(k);i<-i+1
    
67.         repeat
    
68.     endif
    
69. end MERGE
    
70. 
    
71.         复杂度：
    
72.         T(1)=a
    
73.         T(n)=2T(n/2)+cn=2^k*T(1)+kcn;=O(nlogn)
    
74. 
    
75. 快速排序：
    
76.     快速分类：吧小于某元素和大于某元素的元素移动到2边
    
77. procedure QuickSort(p,q)
    
78.     int p,q;global n,A[1:n]
    
79.     if p<q then
    
80.         j=q+1;Partition(p,j)
    
81.         QuickSort(p,j-1);
    
82.         QuickSort(j+1,q);
    
83.     endif
    
84. end QuickSort
    
85. 
    
86. procedure PARTITION(m,p)
    
87.     integer m,p,i;global A(m:p-1)
    
88.     v<-A(m);i<-m
    
89.     loop
    
90.         loop i<-i+1 until A(i)>=v repeat
    
91.         loop p<-p-1 until A(p)<=v repeat
    
92.         if i<p
    
93.             then call INTERCHANGE(A(i),A(p))
    
94.             else exit
    
95.         endif
    
96.     repeat
    
97.     A(m)<-A(P)
    
98. End PARTITION
    
99. 
    
100.         复杂度：
     
101.         最坏情况下O(n^2)，平均O(nlogn)
     
102. 
     

复制代码

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

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

多项式合并：

1. 多项式合并代码：
   
2. // test.cpp : Defines the entry point for the console application.
   
3. //
   
4. 
   
5. #include "stdafx.h"
   
6. 
   
7. #include <stdio.h>
   
8. #include <malloc.h>
   
9. 
   
10. struct ElemType
    
11. {
    
12. ElemType* next;
    
13. float coef;//系数
    
14. int expn;//指数
    
15. };
    
16. 
    
17. ElemType* head1=NULL;
    
18. ElemType* head2=NULL;
    
19. 
    
20. ElemType* CreatePolyn()
    
21. {//初始化多项式
    
22. ElemType* head=(ElemType*)malloc(sizeof(ElemType));
    
23. head->next=NULL;
    
24. return head;
    
25. }
    
26. 
    
27. void AddPolyn(ElemType* head,float coef,int expn)
    
28. {//增加多项式节点
    
29. if(coef == 0.0)
    
30.   return;
    
31. for(ElemType* cur=head;cur->next != NULL && cur->next->expn < expn;cur=cur->next);
    
32. ElemType* newnode=(ElemType*)malloc(sizeof(ElemType));
    
33. newnode->next=cur->next;
    
34. newnode->coef=coef;
    
35. newnode->expn=expn;
    
36. cur->next=newnode;
    
37. }
    
38. 
    
39. void PrintPolyn(ElemType* head)
    
40. {//打印多项式
    
41. for(ElemType* cur=head->next;cur != NULL;cur=cur->next)
    
42. {
    
43.   printf("coef:%f,expn=%d\n",cur->coef,cur->expn);
    
44. }
    
45. }
    
46. 
    
47. void MergePolyn(ElemType* head1,ElemType* head2)
    
48. {//合并多项式head1+head2->head1
    
49. ElemType* cur1=head1;
    
50. 
    
51. while(cur1->next && head2->next)
    
52. {
    
53.   ElemType* cur2=head2->next;
    
54. 
    
55.   if(cur2->expn < cur1->next->expn)//插入cur1之前
    
56.   {
    
57.    head2->next=cur2->next;
    
58.    cur2->next=cur1->next;
    
59.    cur1->next=cur2;
    
60.   }
    
61.   else if(cur2->expn == cur1->next->expn)
    
62.   {
    
63.    cur1->next->coef += cur2->coef;
    
64.    
    
65.    if(cur1->next->coef == 0)
    
66.    {
    
67.     ElemType* p=cur1->next;
    
68.     cur1->next=p->next;
    
69.     delete p;
    
70.    }
    
71.    else
    
72.    {
    
73.     cur1=cur1->next;
    
74.    }
    
75.    head2->next=cur2->next;
    
76.    delete cur2;
    
77.   }
    
78.   else
    
79.   {
    
80.    cur1=cur1->next;
    
81.   }
    
82. 
    
83. }
    
84. 
    
85. if(head2->next)
    
86.   cur1->next=head2->next;
    
87. head2->next=NULL;
    
88. }
    
89. 
    
90. void DestroyPolyn(ElemType* head)
    
91. {//销毁多项式
    
92. ElemType* cur=head;
    
93. while(cur->next)
    
94. {
    
95.   ElemType* p=cur->next;
    
96.   delete cur;
    
97.   cur=p;
    
98. }
    
99. }
    
100. 
     
101. int main(int argc, char* argv[])
     
102. {
     
103. head1=CreatePolyn();
     
104. head2=CreatePolyn();
     
105. //7+3x+9x^8+5x^17
     
106. AddPolyn(head1,7,0);
     
107. AddPolyn(head1,3,1);
     
108. AddPolyn(head1,9,8);
     
109. AddPolyn(head1,5,17);
     
110. printf("head1:\n");
     
111. PrintPolyn(head1);
     
112. 
     
113. //8x+22x^7-9x^8
     
114. AddPolyn(head2,8,1);
     
115. AddPolyn(head2,22,7);
     
116. AddPolyn(head2,-9,8);
     
117. printf("head2:\n");
     
118. PrintPolyn(head2);
     
119. 
     
120. MergePolyn(head1,head2);
     
121. printf("head1:\n");
     
122. PrintPolyn(head1);
     
123. printf("head2:\n");
     
124. PrintPolyn(head2);
     
125. DestroyPolyn(head1);
     
126. DestroyPolyn(head2);
     
127. 
     
128. getchar();
     
129. return 0;
     
130. }
     

复制代码

1. 单链表头结点移动到链表最后：
   
2.     Status A(LinList L)
   
3.     {
   
4.         if(L && L->next)   
   
5.         {
   
6.             Q=L;
   
7.             L=L->next;
   
8.             P=L;
   
9.             while(P->next) P=P->next;
   
10.             P->next=Q;
    
11.             Q->next=NULL;
    
12.         }
    
13.         return OK;
    
14.     }
    
15. 
    
16. 双链表拆分成2个双链表
    
17.     void BB(LNode* s,LNode* q)
    
18.     {
    
19.         p=s;
    
20.         while(p->next != q)
    
21.             p=p->next;
    
22.         p->next=s;
    
23.     }
    
24. 
    
25.     void AA(LNode* pa,LNode* pb)
    
26.     {
    
27.         BB(pa,pb);
    
28.         BB(pb,pa);
    
29.     }
    
30. 
    
31. 10进制转换为8进制
    
32.     void conversion()
    
33.     {
    
34.         InitStack(S);
    
35.         scanf("%d",N);
    
36.         while(N)
    
37.         {
    
38.             Push(S,N%8);
    
39.             N=N/8;
    
40.         }
    
41.         while(!StackEmpty(s))
    
42.         {
    
43.             Pop(S,e);
    
44.             printf("%d",e);
    
45.         }
    
46.     }

复制代码