然后,我们可以通过学习/记忆,知道有一种随机选取算法。在队列中随便找
一个数,如x,用x来分割队列成两部分,比x小的放在左,比x大的放在右,
如果最后发现x所在的位置就是我们需要的位置,那么就得到了我们所要的。
否则,如果x比我们想要的r值小,则在右边再选一个x值进行同样的分割,
否则,在x的左边进行相同的操作。
这种方法的worst-case为O(n^2),但由于我们通过随机选择,所以,可以用
均值/期望值来作为算法的复杂度,可以证明是O(n)。有人要求证明吗?如果我
还没有疯掉,我可能在下一楼给出证明。
原帖由 decisiontree 于 21-5-2009 13:44 发表
我觉得这个方法不错,但对多个数组的比较会有困难。如三个数组的n/3 position的比较结果不是BINARY的值。那如何决定后续指针的移动方向。
我对每列(n/5个元素)中间元素的找法有怀疑。如何保证在线性时间找到非排序的列的中间元素,即在n/5个元素中找第n/10个元素。
原帖由 key 于 21-5-2009 17:03 发表
这个问题不难解决,如果是两个数组,那可以一个天一个地(即ceiling/floor)即可,如果是三个数字,那就可以按顺序0,1,2这样来排余数。
总之,想办法让总长度为n即可。显然,要做到这一点并不难,只是做个决定怎 ...
原帖由 decisiontree 于 21-5-2009 18:17 发表
呵呵,恕我愚笨。我知道总长度为n。请明确解释下三个数组的问题。特别是排在中间那个数组的指针走向,向左走还是向右走。然后看看这个办法能不能用到一百一千个数组里。
相信没有什么东西比一段代码更有说服力了
原帖由 key 于 21-5-2009 21:51 发表
原来的算法说可增可减,事实上是不应该减的,而是每次都从各自的base那里开始增一定量。
获取pace的方法也不是通过n/b^k这样的方式,而是通过剩余长度/b的方法
最后就是每次比较后,只有最小的那个队列的base增大, ...
原帖由 decisiontree 于 22-5-2009 01:57 发表
兄弟写代码辛苦了。我看了一百二十多行,被看晕了。
汗自己(有COMMNENTS可能会好点)。大概知道你的意思了。但我还没法证明它是线性复杂度。
原帖由 key 于 22-5-2009 08:42 发表
写代码是最容易的阶段了,hoho~
其实上面说到的有两个不同的问题,这个算法是O(lgn)的复杂度,算法的核心是69行开始至115行的一个while循环,步进的处理在96至114,重点是两点:
1. 找到最小的行
2. 让最小的 ...
原帖由 key 于 21-5-2009 21:51 发表
原来的算法说可增可减,事实上是不应该减的,而是每次都从各自的base那里开始增一定量。
获取pace的方法也不是通过n/b^k这样的方式,而是通过剩余长度/b的方法
最后就是每次比较后,只有最小的那个队列的base增大, ...
原帖由 绿衣 于 23-5-2009 23:43 发表
如果说对O(n)还有感觉的话,可是n^2、 lgN和更复杂的..具体是怎么算出来的有比较容易掌握的方法吗?很多书和资料只给出个复杂度是多少,实在让我为难啊![]()
Notation | Name | Example |
constant | Determining if a number is even or odd; using a constant-size lookup table or hash table | |
inverse Ackermann | Amortized time per operation using a disjoint set | |
iterated logarithmic | The find algorithm of Hopcroft and Ullman on a disjoint set | |
log-logarithmic | Amortized time per operation using a bounded priority queue[4] | |
logarithmic | Finding an item in a sorted array with a binary search | |
polylogarithmic | Deciding if n is prime with the AKS primality test | |
fractional power | Searching in a kd-tree | |
linear | Finding an item in an unsorted list; adding two n-digit numbers | |
linearithmic, loglinear, or quasilinear | Performing a Fast Fourier transform; heapsort, or merge sort | |
quadratic | Multiplying two n-digit numbers by a simple algorithm; adding two n×n matrices; bubble sort, shell sort,quicksort, or insertion sort | |
cubic | Multiplying 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 algebraic | Tree-adjoining grammar parsing; maximum matching for bipartite graphs (grows faster than cubic if and only if c > 3) | |
L-notation | Factoring a number using the special or general number field sieve | |
exponential orgeometric | Finding the (exact) solution to the traveling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute force | |
factorial or combinatorial | Solving 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 exponential | Deciding the truth of a given statement in Presburger arithmetic |
原帖由 coredump 于 24-5-2009 10:52 发表
NotationNameExampleconstantDetermining if a number is even or odd; using a constant-size lookup table or hash tablehttp://upl ...
欢迎光临 FreeOZ论坛 (https://www.freeoz.org/ibbs/) | Powered by Discuz! X3.2 |