FreeOZ论坛

标题: 两个有序数组中找第n个数（其中n小于任何一个数组的长度） [打印本页]
作者: key    时间: 20-5-2009 20:11
标题: 两个有序数组中找第n个数（其中n小于任何一个数组的长度）
有数组A和B，都是按从小到大的排序。现在需要从这两个数组中找到第n大的数。

最简单的做法：
逐次比较A和B两个数组，并移动比较指针，直到能找到第n个数。这样的算法复杂度为O(n)

更有效的方法在二楼说（如果能占上的话）
作者: key    时间: 20-5-2009 20:23
标题: O(lgn)的算法
1. 在A、B中分别取长度为n/2的部分，比较A[n/2]和B[n/2]，如相等，则A[n/2]或B[n/2]为所求。
2. 不失一般性，假设A[n/2]<B[n/2]，在A[n/2]之后取多n/4个数，而B则取前n/4个数，比较A[(3n)/4]和B[n/4]的值，如果相等，则找到所求，否则转3
3. 假设这时B[n/4] < A[(3n)/4]，则在B[n/4]之取多B[n/8]个数，而A[n/2]后取多A[n/8]个数，比较之。。。。

最多经过lg(n)次的比较后，我们可以得到排第n位的那个数了。算法描述：

假设第k次比较时，A数组取的位置为x，而B数组取的位置为y，不失一般性，假设A[x] < B[y]，则下次比较的位置为：
A[x + n/(2^k)]
B[y - n/(2^k)]，注意，这里需要使 x + n/(2^k) + y - n/(2^k) == n，而因为整除问题，需要做一定的调节。
直到 n/2^k==0
而k=1时, x = n/2, y = n/2

显然，这样的算法时间复杂度为 O(lg(n))
作者: key    时间: 20-5-2009 20:25
对于3个数组，则每次递增或递减的pace可以设为n/3^k，对于s个数组，可以设定为n/s^k。。。。这个没有验算过。
作者: klux    时间: 20-5-2009 20:29
同样找第k大的数，要是只有一个数组，但数组是无序的呢？
作者: coredump    时间: 20-5-2009 20:55
原帖由 klux 于 20-5-2009 20:29 发表

                               
登录/注册后可看大图

同样找第k大的数，要是只有一个数组，但数组是无序的呢？
先排序
作者: key    时间: 20-5-2009 23:00
原帖由 klux 于 20-5-2009 20:29 发表

                               
登录/注册后可看大图

同样找第k大的数，要是只有一个数组，但数组是无序的呢？


这样的题目如果不是要考你的应变能力，就是考你的记忆力了。hoho~

首先，最简单、最容易想到的算法就是先排序，然后再给出目标元素。
随便找一种O(nlogn)的排队算法，比如插入排队，于是我们可以得到一个
时间复杂性为O(nlogn)的算法

然后，我们可以通过学习/记忆，知道有一种随机选取算法。在队列中随便找
一个数，如x，用x来分割队列成两部分，比x小的放在左，比x大的放在右，
如果最后发现x所在的位置就是我们需要的位置，那么就得到了我们所要的。
否则，如果x比我们想要的r值小，则在右边再选一个x值进行同样的分割，
否则，在x的左边进行相同的操作。

这种方法的worst-case为O(n^2)，但由于我们通过随机选择，所以，可以用
均值/期望值来作为算法的复杂度，可以证明是O(n)。有人要求证明吗？如果我
还没有疯掉，我可能在下一楼给出证明。

如果考官还不满意这个“期望值”为O(n)的算法，要求你给出一个worst-case
的算法，而你又没有记得的话，我建议你回家先吧。因为worst-case为O(n)
的算法是计算机算法的一个突破，在1973年由5个变态搞出来，其中两个是
Standford教授，一个是普林斯顿，一个是MIT的，还有一个是CMU的。

这个算法的大致做法是把所有n个元素分成5组，并行列出：
o o o o o o o o o o o o o
o o o o o o o o o o o o o
o o o o o o o o o o o o o
o o o o o o o o o o o o
o o o o o o o o o o o o
对每一列的元素进行中间元素的查找，把找到的中间元素放在中间。
然后对中间一行的中间元素进行中值查找（即在n/5个元素中做中值查找），
把找到的中值置中（连同其对应的列）。于是可以得到左上角的 3 * n / 10个元素
小于中值，而右下角的 3 * n / 10 个元素大于中值。如果你要找的元素在1 ~ 7n/10
之间，就不要在右下角找，如果你要找的元素在 3n/10 ~ n 之间，就不要在左上角找。
由这样的方法，递归得到你要的第r个元素。

可证明，这样的操作能在线性时间内获得第 r 个元素。希望我没有表述错误。

[ 本帖最后由 key 于 20-5-2009 23:04 编辑 ]
作者: klux    时间: 20-5-2009 23:10
赞，都讲到了
作者: key    时间: 20-5-2009 23:12
原帖由 klux 于 20-5-2009 23:10 发表

                               
登录/注册后可看大图

赞，都讲到了


谢谢你提了这个问题，我刚才翻书去了
作者: coredump    时间: 20-5-2009 23:52
原帖由 key 于 20-5-2009 23:12 发表

                               
登录/注册后可看大图



谢谢你提了这个问题，我刚才翻书去了


你就是我们的key啊

key兄现在研究什么领域呢？你功底真扎实啊！
作者: key    时间: 21-5-2009 01:22
然后，我们可以通过学习/记忆，知道有一种随机选取算法。在队列中随便找
一个数，如x，用x来分割队列成两部分，比x小的放在左，比x大的放在右，
如果最后发现x所在的位置就是我们需要的位置，那么就得到了我们所要的。
否则，如果x比我们想要的r值小，则在右边再选一个x值进行同样的分割，
否则，在x的左边进行相同的操作。

这种方法的worst-case为O(n^2)，但由于我们通过随机选择，所以，可以用
均值/期望值来作为算法的复杂度，可以证明是O(n)。有人要求证明吗？如果我
还没有疯掉，我可能在下一楼给出证明。


我尝试证明一下这个东西。很容易证明，随机取得的x可以把队列分割后，前半部分刚好有k个元素的概率为
E[Xk] = 1/n，这里 Xk表示为随机取得的x可以把队列分割成前半部分恰好有k个元素的随机变量。

一次操作，可能得到的分割情况有：(0, n-1), (1, n-2), ..., (k-1, n-k), ..., (n-1, 0)，共n中情况，
分割后，最坏的情况是要找到的r在大的那边，这样下一次分割的 n 值就为 max(k-1, n-k)。

一次分割操作所需的时间复杂度为 O(n)，所以整个查找时间T(n)为
T(n) <= sum(Xk * T(max(k-1, n-k)) + O(n)  (1)
这里sum是从k=1 to n的。
对(1)式求期望值，得到
E[T(n)] <= E[sum[Xk * T(max(k-1, n-k)] + O(n) (2)
= E[Xk] * sum(E[T(max(k-1, n-k)]) + O(n) (3)
= (1/n) * sum(E[T(max(k-1, n-k)]) + O(n)  (4)
= (2/n) * sum(E[T(k)]) + O(n) (5)  这里的sum表示的是k = n/2 to n这部分的值

这个证明的目标是E[T(n)] = O(n)，那这里我们就设定T(k) = ck，如果(5)代入后成立，则证明成功
代入后得到：
E[T(n)] <= (2/n) * sum(E[ck]) + O(n) = (2/n) * c * sum(k) + 0(n) (6)

显然有sum(k) == (3/8)n^2（等差数列求和）
E[T(n)] <= (2/n) * c * (3/8) n + O(n) = (3/4) * c * n + O(n) = c * n - ((1/4)*c*n - O(n)) (7)

由7式可知，当c为足够大的数时，不等式成立，由此可证明 E[T(n)] = O(n)
作者: key    时间: 21-5-2009 01:26
原帖由 coredump 于 20-5-2009 23:52 发表

                               
登录/注册后可看大图



你就是我们的key啊

key兄现在研究什么领域呢？你功底真扎实啊！


过奖了，都是google + 一大堆书的结果。哪可能记得这么多东西呢。

最近闲置在家，以看书为乐。市场不好，加之自己不太了解市场，只能先闲置一段时间了。
作者: someonehappy    时间: 21-5-2009 12:04
找到资料都能理解的话，也是牛人了。
作者: decisiontree    时间: 21-5-2009 13:44
原帖由 key 于 20-5-2009 20:25 发表

                               
登录/注册后可看大图

对于3个数组，则每次递增或递减的pace可以设为n/3^k，对于s个数组，可以设定为n/s^k。。。。这个没有验算过。


我觉得这个方法不错，但对多个数组的比较会有困难。如三个数组的n/3 position的比较结果不是ＢＩＮＡＲＹ的值。那如何决定后续指针的移动方向。
作者: decisiontree    时间: 21-5-2009 14:06
[quote]原帖由 key 于 20-5-2009 23:00 发表

                               
登录/注册后可看大图


这个算法的大致做法是把所有n个元素分成5组，并行列出：
o o o o o o o o o o o o o
o o o o o o o o o o o o o
o o o o o o o o o o o o o
o o o o o o o o o o o o
o o o o o o o o o o o o
对每一列的元素进行中间元素的查找，把找到的中间元素放在中间。
然后对中间一行的中间元素进行中值查找（即在n/5个元素中做中值查找），
把找到的中值置中（连同其对应的列）。。。

》》》
我对每列（n/5个元素）中间元素的找法有怀疑。如何保证在线性时间找到非排序的列的中间元素，即在n/5个元素中找第n/10个元素。
作者: lavahx    时间: 21-5-2009 14:21
找个O(N)排序算法不是很好吗
作者: key    时间: 21-5-2009 17:03
原帖由 decisiontree 于 21-5-2009 13:44 发表

                               
登录/注册后可看大图



我觉得这个方法不错，但对多个数组的比较会有困难。如三个数组的n/3 position的比较结果不是ＢＩＮＡＲＹ的值。那如何决定后续指针的移动方向。


这个问题不难解决，如果是两个数组，那可以一个天一个地（即ceiling/floor）即可，如果是三个数字，那就可以按顺序0,1,2这样来排余数。
总之，想办法让总长度为n即可。显然，要做到这一点并不难，只是做个决定怎样摆就行了。
作者: key    时间: 21-5-2009 17:05
我对每列（n/5个元素）中间元素的找法有怀疑。如何保证在线性时间找到非排序的列的中间元素，即在n/5个元素中找第n/10个元素。


这个问题是一个递归问题。先假设T(n)为线性，那当然我们可以用线性的时间处理T(n/5)了。
作者: key    时间: 21-5-2009 17:39
原帖由 lavahx 于 21-5-2009 14:21 发表

                               
登录/注册后可看大图

找个O(N)排序算法不是很好吗


你说得很对。O(n)排序真的很神奇，不过三种典型的O(n)排序，包括计数排序、Radix排序和Bucket排序都有一定的条件制约。
比如Radix排序，我需要找一个合适的radix来排。从某种意义上，通用性受制约。

当然，这应该是一种选择。
作者: decisiontree    时间: 21-5-2009 18:17
原帖由 key 于 21-5-2009 17:03 发表

                               
登录/注册后可看大图



这个问题不难解决，如果是两个数组，那可以一个天一个地（即ceiling/floor）即可，如果是三个数字，那就可以按顺序0,1,2这样来排余数。
总之，想办法让总长度为n即可。显然，要做到这一点并不难，只是做个决定怎 ...


呵呵，恕我愚笨。我知道总长度为n。请明确解释下三个数组的问题。特别是排在中间那个数组的指针走向，向左走还是向右走。然后看看这个办法能不能用到一百一千个数组里。
作者: key    时间: 21-5-2009 21:06
原帖由 decisiontree 于 21-5-2009 18:17 发表

                               
登录/注册后可看大图



呵呵，恕我愚笨。我知道总长度为n。请明确解释下三个数组的问题。特别是排在中间那个数组的指针走向，向左走还是向右走。然后看看这个办法能不能用到一百一千个数组里。


相信没有什么东西比一段代码更有说服力了。我用C语言实现了上面说的那个算法。
  1.   1 #include <stdio.h>
  2.   2 #include <stdlib.h>
  3.   3 #include <unistd.h>
  4.   4 #include <sys/types.h>
  5.   5 #include <time.h>
  6.   6 #include <values.h>
  7.   7 #include <string.h>
  8.   8
  9.   9
  10. 10 /*
  11. 11  * randomly choose the len of array A , B  and C from 1024 to 2048
  12. 12  * and randomly choose the value of <i>th from 100 to 500
  13. 13  *
  14. 14  * note that the start index of C array is 0 and the start number of ith is 1
  15. 15  *
  16. 16  */
  17. 17
  18. 18 void generate(int x[], size_t len)
  19. 19 {
  20. 20     int k;
  21. 21
  22. 22     for(k=0; k<len; k++)
  23. 23     {
  24. 24         x[k] = rand() % 9999;
  25. 25     }
  26. 26 }
  27. 27
  28. 28 int value_compare(const void * v1, const void * v2)
  29. 29 {
  30. 30     const int * vv1 = (const int *)v1;
  31. 31     const int * vv2 = (const int *)v2;
  32. 32
  33. 33     return (* vv1) - (* vv2);
  34. 34 }
  35. 35
  36. 36 int main(int argc, char ** argv)
  37. 37 {
  38. 38     int len[3], tlen;
  39. 39     int * seq[3];
  40. 40     int base[3];
  41. 41     int ith;
  42. 42     int count, lowest_pace;
  43. 43     int k;
  44. 44     int curpace, diff;
  45. 45
  46. 46     srand(time(NULL));
  47. 47
  48. 48     tlen = 0;
  49. 49     for(k=0; k<3; k++)
  50. 50     {
  51. 51         len[k] = rand() % 1024 + 1024;
  52. 52         seq[k] = (int *)malloc(len[k] * sizeof(int));
  53. 53         generate(seq[k], len[k]);
  54. 54         qsort(seq[k], len[k], sizeof(int), value_compare);
  55. 55         tlen += len[k];
  56. 56     }
  57. 57
  58. 58     ith = rand() % 400 + 100;
  59. 59
  60. 60     //debug
  61. 61     printf("N = %d, A = %d, B = %d, C = %d, ith = %d\n", tlen, len[0], len[1], len[2], ith);
  62. 62
  63. 63     count = 0;
  64. 64     lowest_pace = ith / 3;
  65. 65     base[0] = base[1] = base[2] = 0;
  66. 66
  67. 67     int min, minSeq;
  68. 68
  69. 69     while(lowest_pace > 1)
  70. 70     {
  71. 71         printf("DEBUG lowest_pace = %d, A_base = %d, B_base = %d, C_base = %d\n",
  72. 72             lowest_pace, base[0], base[1], base[2]);
  73. 73
  74. 74         diff = ith - (base[0] + base[1] + base[2] + 3 * lowest_pace);
  75. 75         int pace[3];
  76. 76         int k;
  77. 77
  78. 78         minSeq = -1;
  79. 79
  80. 80         pace[0] = pace[1] = pace[2] = lowest_pace;
  81. 81
  82. 82         for(k=0;diff>0; --diff, k++)
  83. 83         {
  84. 84             pace[k]++;
  85. 85         }
  86. 86
  87. 87         int total_pace[3];
  88. 88
  89. 89         for(k=0; k<3; k++)
  90. 90         {
  91. 91             total_pace[k] = base[k] + pace[k];
  92. 92         }
  93. 93
  94. 94
  95. 95         min = MAXINT;
  96. 96
  97. 97         for(k=0; k<3; k++)
  98. 98         {
  99. 99             if(seq[k][total_pace[k]] < min)
  100. 100             {
  101. 101                 min = seq[k][total_pace[k]];
  102. 102                 minSeq = k;
  103. 103             }
  104. 104         }
  105. 105
  106. 106         base[minSeq] += pace[minSeq];
  107. 107
  108. 108         curpace = 0;
  109. 109         for(k=0; k<3; k++)
  110. 110         {
  111. 111             curpace += base[k];
  112. 112         }
  113. 113
  114. 114         lowest_pace = (ith - curpace) / 3;
  115. 115     }
  116. 116
  117. 117     curpace = base[0] + base[1] + base[2];
  118. 118     diff = ith - curpace;
  119. 119
  120. 120
  121. 121     k = 0;
  122. 122
  123. 123     while(diff > 0)
  124. 124     {
  125. 125         min = MAXINT;
  126. 126         minSeq = -1;
  127. 127
  128. 128         for(k=0; k<3; k++)
  129. 129         {
  130. 130             if(min > seq[k][base[k]])
  131. 131             {
  132. 132                 min = seq[k][base[k]];
  133. 133                 //base[k] ++;
  134. 134                 minSeq = k;
  135. 135             }
  136. 136         }
  137. 137
  138. 138         base[minSeq] ++;
  139. 139         diff --;
  140. 140
  141. 141     }
  142. 142
  143. 143     printf("\n");
  144. 144     printf("<%d>th number is %d, seq is %d, base[0] = %d, base[1] = %d, base[2] = %d\n",
  145. 145         ith, seq[minSeq][base[minSeq]-1], minSeq,  base[0], base[1], base[2]);
  146. 146
  147. 147     int * nseq = (int *)malloc(sizeof(int) * tlen);
  148. 148     memcpy(nseq, seq[0], sizeof(int) * len[0]);
  149. 149     memcpy((char *)nseq + len[0] * sizeof(int), seq[1], sizeof(int) * len[1]);
  150. 150     memcpy((char *)nseq + len[0] * sizeof(int) + len[1] * sizeof(int), seq[2], sizeof(int) * len[2]);
  151. 151
  152. 152     qsort(nseq, tlen, sizeof(int), value_compare);
  153. 153
  154. 154     printf("<%d>th should be %d\n", ith, nseq[ith-1]);
  155. 155
  156. 156     return 0;
  157. 157 }
复制代码
测试结果一
  1. N = 4242, A = 1102, B = 1892, C = 1248, ith = 144
  2. DEBUG lowest_pace = 48, A_base = 0, B_base = 0, C_base = 0
  3. DEBUG lowest_pace = 32, A_base = 0, B_base = 48, C_base = 0
  4. DEBUG lowest_pace = 21, A_base = 0, B_base = 48, C_base = 32
  5. DEBUG lowest_pace = 14, A_base = 22, B_base = 48, C_base = 32
  6. DEBUG lowest_pace = 9, A_base = 22, B_base = 62, C_base = 32
  7. DEBUG lowest_pace = 6, A_base = 22, B_base = 62, C_base = 41
  8. DEBUG lowest_pace = 4, A_base = 22, B_base = 62, C_base = 47
  9. DEBUG lowest_pace = 2, A_base = 27, B_base = 62, C_base = 47

  11. <144>th number is 323, seq is 1, base[0] = 29, base[1] = 68, base[2] = 47
  12. <144>th should be 323
复制代码
测试结果二
  1. N = 5364, A = 1788, B = 2025, C = 1551, ith = 220
  2. DEBUG lowest_pace = 73, A_base = 0, B_base = 0, C_base = 0
  3. DEBUG lowest_pace = 49, A_base = 0, B_base = 73, C_base = 0
  4. DEBUG lowest_pace = 32, A_base = 49, B_base = 73, C_base = 0
  5. DEBUG lowest_pace = 22, A_base = 49, B_base = 73, C_base = 32
  6. DEBUG lowest_pace = 14, A_base = 71, B_base = 73, C_base = 32
  7. DEBUG lowest_pace = 9, A_base = 71, B_base = 88, C_base = 32
  8. DEBUG lowest_pace = 6, A_base = 71, B_base = 88, C_base = 41
  9. DEBUG lowest_pace = 4, A_base = 71, B_base = 88, C_base = 47
  10. DEBUG lowest_pace = 3, A_base = 76, B_base = 88, C_base = 47
  11. DEBUG lowest_pace = 2, A_base = 76, B_base = 91, C_base = 47

  13. <220>th number is 418, seq is 2, base[0] = 77, base[1] = 94, base[2] = 49
  14. <220>th should be 418
复制代码
测试结果三：
  1. N = 4915, A = 2045, B = 1040, C = 1830, ith = 345
  2. DEBUG lowest_pace = 115, A_base = 0, B_base = 0, C_base = 0
  3. DEBUG lowest_pace = 76, A_base = 115, B_base = 0, C_base = 0
  4. DEBUG lowest_pace = 51, A_base = 115, B_base = 0, C_base = 76
  5. DEBUG lowest_pace = 34, A_base = 115, B_base = 51, C_base = 76
  6. DEBUG lowest_pace = 22, A_base = 150, B_base = 51, C_base = 76
  7. DEBUG lowest_pace = 15, A_base = 150, B_base = 51, C_base = 98
  8. DEBUG lowest_pace = 10, A_base = 150, B_base = 66, C_base = 98
  9. DEBUG lowest_pace = 7, A_base = 150, B_base = 66, C_base = 108
  10. DEBUG lowest_pace = 4, A_base = 157, B_base = 66, C_base = 108
  11. DEBUG lowest_pace = 3, A_base = 157, B_base = 66, C_base = 112
  12. DEBUG lowest_pace = 2, A_base = 161, B_base = 66, C_base = 112

  14. <345>th number is 655, seq is 2, base[0] = 164, base[1] = 67, base[2] = 114
  15. <345>th should be 655
复制代码
作者: key    时间: 21-5-2009 21:51
原来的算法说可增可减，事实上是不应该减的，而是每次都从各自的base那里开始增一定量。
获取pace的方法也不是通过n/b^k这样的方式，而是通过剩余长度/b的方法
最后就是每次比较后，只有最小的那个队列的base增大，否则某个队列的增长就有可能过快，
导致结果错误（这个证明谁来做一下？）

基于第三点，如果有成百上千个队列，采用这样的方式来查找，可能效率不是太高，
也就是base case的值需要很大，lg(n)的效率才显示出来
作者: klux    时间: 21-5-2009 22:25
相信没有什么东西比一段代码更有说服力了


这个不能认同。数学证明才有说服力。代码受到程序语言与运行环境的约束并不总是准确
作者: key    时间: 22-5-2009 01:08
原帖由 klux 于 21-5-2009 22:25 发表

                               
登录/注册后可看大图



这个不能认同。数学证明才有说服力。代码受到程序语言与运行环境的约束并不总是准确


哈哈。。。扛王
作者: decisiontree    时间: 22-5-2009 01:57
原帖由 key 于 21-5-2009 21:51 发表

                               
登录/注册后可看大图

原来的算法说可增可减，事实上是不应该减的，而是每次都从各自的base那里开始增一定量。
获取pace的方法也不是通过n/b^k这样的方式，而是通过剩余长度/b的方法
最后就是每次比较后，只有最小的那个队列的base增大， ...


兄弟写代码辛苦了 。我看了一百二十多行，被看晕了。 汗自己（有COMMNENTS可能会好点）。大概知道你的意思了。但我还没法证明它是线性复杂度。
作者: key    时间: 22-5-2009 08:42
原帖由 decisiontree 于 22-5-2009 01:57 发表

                               
登录/注册后可看大图



兄弟写代码辛苦了 。我看了一百二十多行，被看晕了。 汗自己（有COMMNENTS可能会好点）。大概知道你的意思了。但我还没法证明它是线性复杂度。


写代码是最容易的阶段了，hoho~
其实上面说到的有两个不同的问题，这个算法是O(lgn)的复杂度，算法的核心是69行开始至115行的一个while循环，步进的处理在96至114，重点是两点：
1. 找到最小的行
2. 让最小的行的base步进
3. 设置下一次的最短步进距离
而82至85行是用来微调各个队列的步进，使之加起来总和为 n 。这个地方我写得不赖。

由上面的1，2点，确保了每次至少步进lowest_pace的距离。而第3点确保了lowest_pace大致上等于lg(ith)， 整个算法的时间复杂度为lg(ith)
作者: key    时间: 22-5-2009 08:47
原帖由 key 于 22-5-2009 08:42 发表

                               
登录/注册后可看大图



写代码是最容易的阶段了，hoho~
其实上面说到的有两个不同的问题，这个算法是O(lgn)的复杂度，算法的核心是69行开始至115行的一个while循环，步进的处理在96至114，重点是两点：
1. 找到最小的行
2. 让最小的 ...


不是说两点吗？写出来是三点，哈哈。。。。真是
作者: decisiontree    时间: 22-5-2009 12:57
原帖由 key 于 21-5-2009 21:51 发表

                               
登录/注册后可看大图

原来的算法说可增可减，事实上是不应该减的，而是每次都从各自的base那里开始增一定量。
获取pace的方法也不是通过n/b^k这样的方式，而是通过剩余长度/b的方法
最后就是每次比较后，只有最小的那个队列的base增大， ...


我觉得减是需要的，最小队列成功步进后，最大队列因该相应步退（如果没有退成比当前最小队列还小的值），才能保证总值n不变。
作者: 绿衣    时间: 23-5-2009 21:37
标题: 这么多高人啊，简直要崇拜了。。。
算法复杂度是我的软肋了，一听就头大，都怪数据结构老师长得抱歉、教得也太抱歉了 。可是偏偏去年碰到几个面试/笔试就有，有什么比较容易的办法不？大家帮忙给个意见？
作者: coredump    时间: 23-5-2009 22:24
标题: 回复 #28 绿衣 的帖子
学算法得沉得下心，耐着性子，慢慢培养兴趣，还得亲自动手，多写点C代码，这方面我也很差
作者: 绿衣    时间: 23-5-2009 23:43
标题: 同意啊，算法需要多练多看。还是想知道对O( x )括号里那个怎么确定有方法/技巧吗？
如果说对O(n)还有感觉的话，可是n^2、 lgN和更复杂的..具体是怎么算出来的有比较容易掌握的方法吗？很多书和资料只给出个复杂度是多少，实在让我为难啊
作者: klux    时间: 23-5-2009 23:49
原帖由 绿衣 于 23-5-2009 23:43 发表

                               
登录/注册后可看大图

如果说对O(n)还有感觉的话，可是n^2、 lgN和更复杂的..具体是怎么算出来的有比较容易掌握的方法吗？很多书和资料只给出个复杂度是多少，实在让我为难啊


说明你看的书不好
有空的话看introduction to algorithm，没空的话就看看wiki吧
作者: coredump    时间: 24-5-2009 10:52
标题: 对看wiki基本上就够了
NotationNameExample

                               
登录/注册后可看大图
constantDetermining if a number is even or odd; using a constant-size lookup table or hash table

                               
登录/注册后可看大图
inverse AckermannAmortized time per operation using a disjoint set

                               
登录/注册后可看大图
iterated logarithmicThe find algorithm of Hopcroft and Ullman on a disjoint set

                               
登录/注册后可看大图
log-logarithmicAmortized time per operation using a bounded priority queue[4]

                               
登录/注册后可看大图
logarithmicFinding an item in a sorted array with a binary search

                               
登录/注册后可看大图
polylogarithmicDeciding if n is prime with the AKS primality test

                               
登录/注册后可看大图
fractional powerSearching in a kd-tree

                               
登录/注册后可看大图
linearFinding an item in an unsorted list; adding two n-digit numbers

                               
登录/注册后可看大图
linearithmic, loglinear, or quasilinearPerforming a Fast Fourier transform; heapsort, or merge sort

                               
登录/注册后可看大图
quadraticMultiplying two n-digit numbers by a simple algorithm; adding two n×n matrices; bubble sort, shell sort,quicksort, or insertion sort

                               
登录/注册后可看大图
cubicMultiplying two n×n matrices by simple algorithm; finding the shortest path on a weighted digraph with theFloyd-Warshall algorithm; inverting a (dense) nxn matrix using LU or Cholesky decomposition

                               
登录/注册后可看大图
polynomial or algebraicTree-adjoining grammar parsing; maximum matching for bipartite graphs (grows faster than cubic if and only if c > 3)

                               
登录/注册后可看大图


                               
登录/注册后可看大图
L-notationFactoring a number using the special or general number field sieve

                               
登录/注册后可看大图
exponential orgeometricFinding the (exact) solution to the traveling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute force

                               
登录/注册后可看大图
factorial or combinatorialSolving the traveling salesman problem via brute-force search; finding the determinant with expansion by minors. The statement

                               
登录/注册后可看大图
is sometimes weakened to

                               
登录/注册后可看大图
to derive simpler formulas for asymptotic complexity.

                               
登录/注册后可看大图
double exponentialDeciding the truth of a given statement in Presburger arithmetic
作者: key    时间: 24-5-2009 16:17
原帖由 coredump 于 24-5-2009 10:52 发表

                               
登录/注册后可看大图

NotationNameExample

                               
登录/注册后可看大图
constantDetermining if a number is even or odd; using a constant-size lookup table or hash tablehttp://upl ...


背O()呀？
推荐看＜Data Structures, Algorithms, and Applications in C++＞，Sartaj Sahni，
中文版＜数据结构、算法与应用－－C＋＋语言描述＞，机械工业出版社，汪诗林等译
这本书第二章 程序性能中对于时间复杂性的讨论比较好，有空可以看一下。

然后就是klux说的MIT的Introduction to Algorithm，但这本书主要是数学计算，不头昏可以看一下



欢迎光临 FreeOZ论坛 (https://www.freeoz.org/ibbs/) Powered by Discuz! X3.2