及其对于,递归算法优化永利澳门游戏网址304:

递归算法及优化,递归算法优化

 1 package interview;
 2 //有一个斐波那契数列计算的函数,最前面的k个数为1,后面的没一位是前k位之和,例如k=4,该函数
 3 //该函数返回值为1,1,1,1,4,7,13,25,49
 4 public class RecursiveOptimize {
 5     static int  fib_k(int n,int k) {
 6          if(n<k) 
 7             return 1;
 8          int result = 0;
 9          for(int i=0;i<k;i++){
10              result += fib_k(n-i-1,k);
11          }
12          return result;
13     }
14     static int fib_k_optimize(int n,int k) {
15         if(n<k)
16             return 1;
17         int[] fib = new int[n+1];
18         for(int i=0;i<k;i++){
19             fib[i]=1;
20         }
21         for(int i=k;i<=n;i++) {
22             int result = 0;
23             for(int j=0;j<k;j++){
24                 result += fib[i-j-1];
25             }
26             fib[i]=result;
27         }
28         return fib[n];
29     }
30     public static void main(String[] args) {
31         long start = System.nanoTime();
32         for(int i=0;i<20;i++){
33             System.out.print(fib_k(i,4)+" ");
34         }
35         long end = System.nanoTime();
36         System.out.println("n"+(end-start));
37         
38         //===================================
39         start = System.nanoTime();
40         for(int i=0;i<20;i++){
41             System.out.print(fib_k_optimize(i,4)+" ");
42         }
43         end = System.nanoTime();
44         System.out.println("n"+(end-start));
45     }
46     
47 }

 

1 package interview;
2 //
有多少个斐波那契数列计算的函数,最前边的k个数为1,前边的没一人是前k位之和,比方…

题材陈述

给定一个整数数组a[0,…,n-1],求数组中第k小数

输入描述

第生机勃勃输入数老总度n和k,在这之中1<=n<=5000, 1<=k<=n

接下来输出n个整产生分,每种数的界定[1, 5000]

输出描述

该数组中第k小数

样例输入

4 2
1 2 3 4

样例输出

2

其实可以用 堆 来做,保证根节点为最小值,然后逐步剔除。不过当然也可以直接排序。
权当熟悉一下STL:

 1 #include <vector>
 2 #include <algorithm>
 3 #include <iostream>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int n, k;
 9     cin >> n >> k;
10 
11     vector<int> a(n, 0);
12     for (int i = 0; i < n; i++)
13     {
14         cin >> a[i];
15     }
16     sort(a.begin(), a.end());
17 
18     cout << a[k-1];
19 
20     return 0;
21 }

 


在和 Space_Double7 讨论后(详见讨论区),于是有了想要比较 快排 和 堆排 对于这道题各自的效率的想法。
于是写了一个程序来比较它们各自的运行时间,程序主要包括 随机生成输入数据、分别用快排和堆排求解并计时、比较 这几个部分。
代码如下:

  1 #include <vector>
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <stdlib.h>
  5 #include <time.h>
  6 #include <windows.h>
  7 
  8 using namespace std;
  9 
 10 // for timing
 11 clock_t start, stop;
 12 double durationOfQsort, durationOfHeapsort;
 13 
 14 vector<int> num;
 15 int k, ans, n;
 16 bool found;
 17 
 18 // 快排: 选定轴点
 19 int parti(int lo, int hi)
 20 {
 21     swap(num[lo], num[lo + rand() % (hi - lo + 1)]);
 22     int pivot = num[lo];
 23     while (lo < hi)
 24     {
 25         while ((lo < hi) && (pivot <= num[hi])) hi--;
 26         num[lo] = num[hi];
 27         while ((lo < hi) && (num[lo] <= pivot)) lo++;
 28         num[hi] = num[lo];
 29     }
 30     num[lo] = pivot;
 31     if (lo == k)
 32     {
 33         found = true; // 表征已确定找到第 k 小数
 34         ans = num[k];
 35     }
 36     return lo;
 37 }
 38 
 39 // 快排主体
 40 void quicksort(int lo, int hi)
 41 {
 42     if ((hi - lo < 2) || (found))
 43     {
 44         if ((!found) && (lo == k))
 45         {
 46             found = true;
 47             ans = num[k];
 48         }
 49         return;
 50     }
 51     int mi = parti(lo, hi - 1);
 52     quicksort(lo, mi);
 53     quicksort(mi + 1, hi);
 54 }
 55 
 56 #define InHeap(n, i)        (( (-1) < (i) ) && ( (i) < (n) ))
 57 #define Parent(i)            ((i-1)>>1)
 58 #define LastInternal(n)        Parent(n-1)
 59 #define LChild(i)            (1+((i) << 1))
 60 #define RChild(i)            ((1+(i)) << 1)
 61 #define LChildValid(n, i)    InHeap(n, LChild(i))
 62 #define RChildValid(n, i)    InHeap(n, RChild(i))
 63 #define Bigger(PQ, i, j)    ((PQ[i])<(PQ[j])? j : i)
 64 #define ProperParent(PQ, n, i) 
 65     (RChildValid(n, i) ? Bigger(PQ, Bigger(PQ, i, LChild(i)), RChild(i)):
 66     (LChildValid(n, i) ? Bigger(PQ, i, LChild(i)):i
 67     )
 68     )
 69 
 70 // 对向量前 n 个元素中的第 i 实施下滤操作
 71 int percolateDown(int n, int i)
 72 {
 73     int j;
 74     while (i != (j = ProperParent(num, n, i)))
 75     {
 76         swap(num[i], num[j]);
 77         i = j;
 78     }
 79     return i;
 80 }
 81 
 82 // Floyd 建堆算法
 83 void heapify()
 84 {
 85     for (int i = LastInternal(n); InHeap(n, i); i--)
 86         percolateDown(n, i);
 87 }
 88 
 89 // 删除堆中最大的元素
 90 int delMax(int hi)
 91 {
 92     int maxElem = num[0]; 
 93     num[0] = num[hi];
 94     percolateDown(hi, 0);
 95     return maxElem;
 96 }
 97 
 98 // 堆排主体
 99 void heapsort()
100 {
101     heapify();
102     int hi = n;
103     while (hi > 0)
104     {
105         --hi;
106         num[hi] = delMax(hi);
107         if (hi == k)
108         {
109             ans = num[k];
110             return;
111         }
112     }
113 }
114 
115 int main()
116 {
117     int scoreOfQsort = 0, scoreOfHeapsort = 0;
118 
119     for (int iter = 0; iter < 30; iter++)
120     {
121         // 确定 n 的大致最大范围,注意随机 n 会有向右 MaxN 的偏差 
122         const int MaxN = 3001;
123         
124         // 产生一个 0..n-1 的随机序列输入数组,n 最大为3000
125         cout << "**********************第" << iter + 1 << "次************************" << endl;
126         //srand(unsigned(clock()));
127         n = rand() % MaxN + MaxN;
128         vector<int> a(n, 0);
129         for (int i = 0; i < n; i++)
130             a[i] = i;
131         random_shuffle(a.begin(), a.end());
132 
133         cout << "产生一个 0.." << n - 1 << " 的随机序列输入数组:" << endl;
134         /*for (int i = 0; i < n; i++)
135             cout << a[i] << " ";*/
136         cout << endl;
137 
138         // 随机生成 k
139         //srand(unsigned(clock()));
140         k = rand() % n;
141         cout << "k = " << k << endl << endl;
142 
143         // 第 k 小的数一定是 k,因为 random_shuffle,同时避免退化情形对快排一般性的影响
144         cout << "在该数组中第 " << k << " 小的数是: " << k << endl << endl << endl;
145 
146         // qsort
147         cout << "快排:" << endl;
148         num = a; 
149         start = clock();
150         found = false;
151         quicksort(0, n);
152         stop = clock();
153         durationOfQsort = ((double)(stop - start)*1000) / CLK_TCK;
154         cout << "Ok.. 我已经找到了第 " << k << " 小的数,它是: " << ans << endl;
155         cout << "快排用时: " << durationOfQsort << "ms" << endl;
156         if (ans != k)
157         {
158             cout << "注意!!!答案错误!!!" << endl;
159             system("pause");
160         }
161         /*else
162         {
163             cout << "此时的序列情况是: ";
164             for (int i = 0; i < n; i++)
165                 cout << num[i] << " ";
166         }*/
167         cout << endl << endl;
168 
169         // heapsort
170         cout << "堆排:" << endl;
171         num = a;
172         start = clock();
173         heapsort();
174         stop = clock();
175         durationOfHeapsort = ((double)(stop - start) * 1000) / CLK_TCK;
176         cout << "Ok.. 我已经找到了第 " << k << " 小的数,它是: " << num[k] << endl;
177         cout << "堆排用时: " << durationOfHeapsort << "ms" << endl;
178         if (num[k] != k)
179         {
180             cout << "注意!!!答案错误!!!" << endl;
181             system("pause");
182         }
183         /*else
184         {
185             cout << "此时的序列情况是: ";
186             for (int i = 0; i < n; i++)
187                 cout << num[i] << " ";
188         }*/
189         cout << endl << endl;
190 
191         if (durationOfHeapsort > durationOfQsort) scoreOfQsort++;
192         else scoreOfHeapsort++;
193     }
194     cout << "*******************END***********************";
195     cout << endl << endl << "总比分(快排:堆排): " << scoreOfQsort << " : " << scoreOfHeapsort;
196     cout << endl;
197 
198     return 0;
199 }

运转了几下,大约能够看出 快排:堆排 的频率比 趋近于
2:1(对于每种case的耗费时间少则计分,计分多的频率高),那是此中 3 次的结果:

永利澳门游戏网址304 1

永利澳门游戏网址304 2

永利澳门游戏网址304 3

感兴趣的能够和睦在本地运转一下~

 


 

而是笔者意识还是留存叁个主题素材,大家主要想谈谈的是 对于 “少年老成找到 第k小
的成分便立马退出”那事 对于一切完全排序本人优化程度的分寸。

横平素看,仅仅相比优化后的排序 耗费时间并不能够鲜明 到底是便捷排序 本人对于自由数据来说比 堆排序 质量好(从上边看,似乎是一望而知的),依然“大器晚成找到 第k小 的因素便随时退出”那么些优化在这里边
帮了飞跃排序的大忙,使其在那地呈现出了更加好的脾气。

纵一直看,大家想看看该优化对于截然排序来说,能优化到哪些水平。

因此笔者主宰比较二种排序 优化退出的日子占完全排序的光阴
的比,来看看那个优化对于截然排序的熏陶程度。

那是改正今后的代码,算的是比例,百分比越小,优化越精晓

  1 #include <vector>
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <stdlib.h>
  5 #include <time.h>
  6 #include <windows.h>
  7 
  8 using namespace std;
  9 
 10 // for timing
 11 clock_t start, stop, stop1;
 12 double durationOfQsort, durationOfHeapsort;
 13 
 14 vector<int> num;
 15 int k, ans, n;
 16 bool found;
 17 double time1, time2;
 18 double average1 = 0, average2 = 0;
 19 
 20 // 快排: 选定轴点
 21 int parti(int lo, int hi)
 22 {
 23     swap(num[lo], num[lo + rand() % (hi - lo + 1)]);
 24     int pivot = num[lo];
 25     while (lo < hi)
 26     {
 27         while ((lo < hi) && (pivot <= num[hi])) hi--;
 28         num[lo] = num[hi];
 29         while ((lo < hi) && (num[lo] <= pivot)) lo++;
 30         num[hi] = num[lo];
 31     }
 32     num[lo] = pivot;
 33     if ((!found)&&(lo == k))
 34     {
 35         stop1 = clock();
 36         found = true;
 37     }
 38     return lo;
 39 }
 40 
 41 // 快排主体
 42 void quicksort(int lo, int hi)
 43 {
 44     if (hi - lo < 2)
 45     {
 46         if ((!found) && (lo == k))
 47         {
 48             stop1 = clock();
 49             found = true;
 50         }
 51         return;
 52     }
 53     int mi = parti(lo, hi - 1);
 54     quicksort(lo, mi);
 55     quicksort(mi + 1, hi);
 56 }
 57 
 58 #define InHeap(n, i)        (( (-1) < (i) ) && ( (i) < (n) ))
 59 #define Parent(i)            ((i-1)>>1)
 60 #define LastInternal(n)        Parent(n-1)
 61 #define LChild(i)            (1+((i) << 1))
 62 #define RChild(i)            ((1+(i)) << 1)
 63 #define LChildValid(n, i)    InHeap(n, LChild(i))
 64 #define RChildValid(n, i)    InHeap(n, RChild(i))
 65 #define Bigger(PQ, i, j)    ((PQ[i])<(PQ[j])? j : i)
 66 #define ProperParent(PQ, n, i) 
 67     (RChildValid(n, i) ? Bigger(PQ, Bigger(PQ, i, LChild(i)), RChild(i)):
 68     (LChildValid(n, i) ? Bigger(PQ, i, LChild(i)):i
 69     )
 70     )
 71 
 72 // 对向量前 n 个元素中的第 i 实施下滤操作
 73 int percolateDown(int n, int i)
 74 {
 75     int j;
 76     while (i != (j = ProperParent(num, n, i)))
 77     {
 78         swap(num[i], num[j]);
 79         i = j;
 80     }
 81     return i;
 82 }
 83 
 84 // Floyd 建堆算法
 85 void heapify()
 86 {
 87     for (int i = LastInternal(n); InHeap(n, i); i--)
 88         percolateDown(n, i);
 89 }
 90 
 91 // 删除堆中最大的元素
 92 int delMax(int hi)
 93 {
 94     int maxElem = num[0]; 
 95     num[0] = num[hi];
 96     percolateDown(hi, 0);
 97     return maxElem;
 98 }
 99 
100 // 堆排主体
101 void heapsort()
102 {
103     heapify();
104     int hi = n;
105     while (hi > 0)
106     {
107         --hi;
108         num[hi] = delMax(hi);
109         if (hi == k) stop1 = clock();
110     }
111 }
112 
113 int main()
114 {
115     // 确定 n 的大致最大范围,注意随机 n 会有向右 MaxN 的偏差 
116     const int MaxN = 3001;
117     
118     // 计算次数
119     const int times = 30;
120 
121     int scoreOfQsort = 0, scoreOfHeapsort = 0;
122 
123     for (int iter = 0; iter < times; iter++)
124     {
125         
126         
127         // 产生一个 0..n-1 的随机序列输入数组,n 最大为3000
128         cout << "**********************第" << iter + 1 << "次************************" << endl;
129         //srand(unsigned(clock()));
130         n = rand() % MaxN + MaxN;
131         vector<int> a(n, 0);
132         for (int i = 0; i < n; i++)
133             a[i] = i;
134         random_shuffle(a.begin(), a.end());
135 
136         cout << "产生一个 0.." << n - 1 << " 的随机序列输入数组:" << endl;
137         /*for (int i = 0; i < n; i++)
138             cout << a[i] << " ";*/
139         cout << endl;
140 
141         // 随机生成 k
142         //srand(unsigned(clock()));
143         k = rand() % n;
144         cout << "k = " << k << endl << endl;
145 
146         // 第 k 小的数一定是 k,因为 random_shuffle,同时避免退化情形对快排一般性的影响
147         cout << "在该数组中第 " << k << " 小的数是: " << k << endl << endl << endl;
148 
149         // qsort
150         cout << "快排:" << endl;
151         num = a; 
152         start = clock();
153         found = false;
154         quicksort(0, n);
155         stop = clock(); 
156         time1 = (double)(stop1 - start) * 1000 / CLK_TCK;
157         time2 = (double)(stop - start) * 1000 / CLK_TCK;
158         cout << "找到 k 的时间: " << time1 << " ms" << endl;
159         cout << "完全排序 的时间: " << time2 << " ms" << endl;
160         durationOfQsort = time1 / time2 * 100;
161         average1 += durationOfQsort;
162         /*cout << "Ok.. 我已经找到了第 " << k << " 小的数,它是: " << ans << endl;*/
163         cout << "快排占比: " << durationOfQsort << " %" << endl;
164         /*if (ans != k)
165         {
166             cout << "注意!!!答案错误!!!" << endl;
167             system("pause");
168         }*/
169         /*else
170         {
171             cout << "此时的序列情况是: ";
172             for (int i = 0; i < n; i++)
173                 cout << num[i] << " ";
174         }*/
175         cout << endl << endl;
176 
177         // heapsort
178         cout << "堆排:" << endl;
179         num = a;
180         start = clock();
181         heapsort();
182         stop = clock();
183         time1 = (double)(stop1 - start) * 1000 / CLK_TCK;
184         time2 = (double)(stop - start) * 1000 / CLK_TCK;
185         cout << "找到 k 的时间: " << time1 << " ms" << endl;
186         cout << "完全排序 的时间: " << time2 << " ms" << endl;
187         durationOfHeapsort = time1 / time2 * 100;
188         average2 += durationOfHeapsort;
189         //cout << "Ok.. 我已经找到了第 " << k << " 小的数,它是: " << num[k] << endl;
190         cout << "堆排占比: " << durationOfHeapsort << " %" << endl;
191         /*if (num[k] != k)
192         {
193             cout << "注意!!!答案错误!!!" << endl;
194             system("pause");
195         }*/
196         /*else
197         {
198             cout << "此时的序列情况是: ";
199             for (int i = 0; i < n; i++)
200                 cout << num[i] << " ";
201         }*/
202         cout << endl << endl;
203 
204         if (durationOfHeapsort > durationOfQsort) scoreOfQsort++;
205         else scoreOfHeapsort++;
206     }
207     cout << "*******************END***********************";
208     cout << endl << endl << "总比分(快排:堆排): " << scoreOfQsort << " : " << scoreOfHeapsort;
209     cout << endl;
210     cout << endl << "快排平均占比: " << average1 / times << " %" << endl;
211     cout << endl << "堆排平均占比: " << average2 / times << " %" << endl;
212 
213     return 0;
214 }

 

 运营 3 次的结果:

永利澳门游戏网址304 4

永利澳门游戏网址304 5

永利澳门游戏网址304 6

 

永利澳门游戏网址304,可见,

1、这一个优化对于二种排序的熏陶程度是大致的(百分比越小,优化越通晓);

2、对于截然排序来讲,它大致约等于在头里加了二个0.6 的全面,也便是 只 干了截然排序
0.6 倍的职业量,正如剖判来看,仍为常周密级的优化。

鉴于数量是截然自由的(并且未有再一次成分),快排也适应得很好,在事实上用旅途(对于相近随机数据),它的频率是中度的。

 


 

不!还没完!

来来来,未来大家重临原难题小编,回到 查找 数组 第
k 小数 那样杰出而基础的主题材料自身上来……

 就算 原问题 数据规模小,水水就会过,可是既然已经鼓捣过了,干脆鼓捣完。

据此本身或许调控写贰个对此周围数占领所普舒心义的玩命优化的算法来消除难点(优化到线性复杂度)。

 

 再思量这一个主题素材,在写了一次快排之后,会开掘那是三个与 快排中甄选轴点 十分的帅似的难题。

轴点是左右聚众的分界点,左集合全部因素比轴点小,右会集全体因素比轴点大,你可以窥见,找第
K 小数正是找在岗位 K 上的轴点(也正如上述优化所想)!

 

而是大家照样要向地点所写的主次同样,找到 k 就退出吗?

 

1、快捷接收算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注