为什么要学习算法和数据结构
Larry, LIU Xinyu
lzprgmr
Blog: http://www.cnblogs.com/baiyanhuang/
Douban:http://www.douban.com/people/baiyanhuang/
Chinainvent
刚刚脱稿：
--
Devymex
求O(n)算法，将数组整理为前n/2部分都小于后n/2部分，但各部分不要求有序。
暂时没有思路。
=========程序控=========
机械唯物主义 : linjunhalida
Devymex
=========程序控=========
Yi Chao
fairywell
Wu Yin
--
滚滚长江东逝水，浪花淘尽英雄。
是非成败转头空。
青山依旧在，几度夕阳红。
白发渔樵江渚上，惯看秋月春风。
一壶浊酒喜相逢。
古今多少事，都付笑谈中。
----------
Email: wyw...@gmail.com
Gtalk: wyw...@gmail.com
MSN: wyw...@hotmail.com
fairywell
Shuo Chen
On Mar 15, 11:29 am, Devymex <devy...@gmail.com> wrote:
> 任意一个长度为数组，可能有正有负，32位范围为界。
>
> 求O(n)算法，将数组整理为前n/2部分都小于后n/2部分，但各部分不要求有序。
>
> 暂时没有思路。
>
> =========程序控 <http://www.cnblogs.com/devymex>=========
>
> 2011/3/14 Chinainvent <chinainvent....@gmail.com>
>
> > 很神奇，此刻居然可以轻松地访问google site而不用翻墙，解禁了？
>
> > 2011/3/14 Larry, LIU Xinyu <liuxiny...@gmail.com>
>
> >> 刚刚脱稿：
>
> >>http://sites.google.com/site/algoxy/introduction
> >> (在墙外)
>
> >> --
> >> LIU
>
> > --
> > Chinainvent
> > Blog:http://blog.csdn.net/chinainvent
> > Work at Alibaba <http://www.alibaba.com>
ma martin
Larry, LIU Xinyu
说一下这个算法的描述：
记序列为xs, length xs = n, 记k=n/2
1. 取xs的第一个元素为pivot
2. partition，将所有小于pivot的元素放在前，记为as，大于的放在后，记为bs，记此时pivot的位置为i;
3. 比较i和k, 若i < k， 则令xs=bs， k = k - i重复1
若i>k则，令xs=as，重复1
复杂度:该算法为线性算法，其中2的实现和quick sort相同。
--
LIU
On Mar 15, 11:56 am, Yi Chao <yichao...@gmail.com> wrote:
> 有O(N)的算法的，请查看算法导论，O(N)找第K大数，常数大点就是了。
>
> 在 2011-3-15，上午11:54， Devymex 写道：
>
> > 嗯，应该是没有，这个问题等价于查找数组中第n/2小的元素，不用哈希的话是没有O(n)的解法的。
>
> > =========程序控=========
>
> > 2011/3/15 Devymex <devy...@gmail.com>
> > 任意一个长度为数组，可能有正有负，32位范围为界。
>
> > 求O(n)算法，将数组整理为前n/2部分都小于后n/2部分，但各部分不要求有序。
>
> > 暂时没有思路。
>
> > =========程序控=========
>
> > 2011/3/14 Chinainvent <chinainvent....@gmail.com>
> > 很神奇，此刻居然可以轻松地访问google site而不用翻墙，解禁了？
>
> > 2011/3/14 Larry, LIU Xinyu <liuxiny...@gmail.com>
free.wang
--
真正的杰出，不是妙用规则的错层，而是极致的偏执于信念.
The Crankiness of Belief achieves Great , not the Trick of Regulation.
Devymex
Yi Chao
Devymex
第一遍，将Hash表置0
第二遍，将数组中存在的元素对应的Hash位置1
第三遍，将Hash表中第i个元素+=第i-1个元素。从1到结束。
这样，Hash表中不为0的元素就是数组中比对应的那个值小的数的个数。
=========程序控=========
Wu Yin
Wu Yin
fairywell
Wang Feng
不要这样灌水好么？
吴教V5 :D在 2011-3-15，下午10:29， Wu Yin 写道：这种简单的partition只是expected O(n)而已，worst case是O(nk)的。那个d&c求pivot的方法才是worst case O(n)的
1 void swap( int& a, int& b )
2 {
3
4 a ^= b;
5 b ^= a;
6 a ^= b;
7 }
8
9 int partation( int* arr, int low, int high )
10 {
11 int ans = low - 1;
12 for ( int i = low; i < high; ++i )
13 {
14 if ( arr[i] < arr[high] )
15 {
16 swap( arr[i], arr[++ans] );
17 }
18 }
19 swap( arr[++ans], arr[high] );
20 return ans;
21 }
22
23 int nth( int* arr, int low, int high, int index )
24 {
25 int mid = partation(arr, low, high);
26 if ( mid == index ) return arr[mid];
27 return
28 ( mid < index ) ?
29 nth(arr, mid+1, high, index) :
30 nth(arr, low, mid-1, index);
31 }
Larry, LIU Xinyu
worst case 是O(n^2)的，此时序列为有序序列，每次pivot都是smallest或者biggest。
average情况下，此算法复杂度期望为：O(n)+O(n/2)+O(n/4)+...=O(n).
一个不那么精确的改良：每次处理xs时，取pivot=median(xs[1], xs[n], xs[n/2])。
这在大多数情况下已经足够健壮了。
--
LIU
On Mar 15, 10:29 pm, Wu Yin <wyw...@gmail.com> wrote:
> 这种简单的partition只是expected O(n)而已，worst case是O(nk)的。
> 那个d&c求pivot的方法才是worst case O(n)的
>
> 2011/3/15 Larry, LIU Xinyu <liuxiny...@gmail.com>
> wywcgs<http://www.topcoder.com/tc?module=MemberProfile&cr=22629546>
fairywell
Wu Yin
Wu Yin
fairywell
Larry, LIU Xinyu
Worst case analysis比较简单，就不细说了。Expected running time的话，比较复杂，需要一个引理和数学期望的
累加计算。这里不大方便写。
我说说最后的改良，如果大家细看STL quick sort的SGI版本，就会发现实际上就是用这个方法选取的pivot。
可以说理论上无意义，但是它可以在很多情况下的避免前面提到的worst case。保证每次partition后，不会形成一侧为空，一侧为满的情
况。
类似的等价方法为pivot = xs[randint(0, length xs)]。除非精心设计一个序列进行exploit，否则对于很多序列，
这类策略足够强壮了。
--
LIU
On Mar 16, 9:48 am, Wu Yin <wyw...@gmail.com> wrote:
> 1. 确实是O(n^2)不是O(nk),我的问题
> 2. 期望虽然是O(n), 可是 不是你这么个算法. 去找找randomized quicksort期望O(nlgn)的分析法,
> 用那种方法可以分析出O(n)的复杂度.
> 3. 最后的改良理论上无意义.
>
> 2011/3/16 Larry, LIU Xinyu <liuxiny...@gmail.com>
> wywcgs<http://www.topcoder.com/tc?module=MemberProfile&cr=22629546>
Wu Yin
Hi,
Larry, LIU Xinyu
我觉得这里说的事情有偏差。我也举一个例子，就是费马检验，我们知道费马检验是存在漏杀的，但是它给出了一种方法。
也就是说通过费马检验的数字很可能是素数了。如果否定这类方法，那么很多问题无法给出目前水平可接受的解。或者成本可以接受的解。
On Mar 16, 11:01 am, Wu Yin <wyw...@gmail.com> wrote:
> 我见过sgi stl的sort.
> 只是既然是在讨论算法, 那就去讨论算法. 和实用没什么太大的关系. 就像那个d&c的O(n)常数很大, 但是他依然是个好算法; fibonacci
> heap实际应用效率不高, 但是它仍然是非常游泳的数据结构一样.
> 至少在算法本身层面上, 你举出一个方法, 就得分析一下它的效果, 单纯说实际效果不错没什么意义. 因为你也不知道实际数据的分布到底是什么样子,
> 这个算法到底是不是真的就是正好对这个分布有很好的performance.
>
> 2011/3/16 Larry, LIU Xinyu <liuxiny...@gmail.com>
> wywcgs<http://www.topcoder.com/tc?module=MemberProfile&cr=22629546>
Wu Yin
Hi,
Larry, LIU Xinyu
并不矛盾啊，Miller-Rabin primary test也是probabilistic search method. 这个方法也是存在漏
杀的
Miller-Rabin(n, s) 的错误概率为1/(2^s)，如果取s足够大，通常我们可以得到一个非常好的结果。
回到前面说的三点中值法，和pivot=xs[randint(0, length xs)]法。也可以计算出出现worst case的可能性很
低。
对于长度为n的序列pivot为max/min的概率为2/n，所以每次pivot都恰好把序列分成一半空，一半满的概率为：
(2^(n-1))/(n!)。
当n=32时，这一概率为：8.16127700206094e-27已经非常小了。
--
LIU
On Mar 16, 11:41 am, Wu Yin <wyw...@gmail.com> wrote:
> 但是你要知道rabin miller给出了一个每次检测的确定下界,所以可以用possibility
> amplify的方法去得到一个正确率无限接近100%的方法.
> 重要的不在idea本身,在于对idea的分析.
>
> 2011/3/16 Larry, LIU Xinyu <liuxiny...@gmail.com>
> wywcgs<http://www.topcoder.com/tc?module=MemberProfile&cr=22629546>
Wu Yin
Hi,
Wang Feng
1） random_shuffle 之后再挑选
2） 如果 长度 N 大于 100000 则随机挑选 64 个元素排序后将剩余数据塞入 65 个空隙后再处理
3） 如果 要挑选的元素序数 m << N 的时候，采用 heap sort
忘记了具体出处了，方才翻看 TAOCP 没有找到
Wu Yin
Hi,
Wu Yin
Hi,
我也感觉这么Re来Re去下去不大好了。我贴一段CLRS 7.2.1的一段：
The worst-case behavior for quicksort occurs when the partitioning
routine produces one subproblem with n - 1 elements and one with 0
elements. (This claim is proved in Section 7.4.1.) Let us assume that
this unbalanced partitioning arises in each recursive call. The
partitioning costs Θ(n) time. Since the recursive call on an array of
size 0 just returns, T(0) = Θ(1), and the recurrence for the running
time is
T(n)
=
T(n - 1) + T(0) + Θ(n)
=
T(n - 1) + Θ(n).
On Mar 16, 1:54 pm, Wu Yin <wyw...@gmail.com> wrote:
> 不想再回了,意义不大了.
> 你这个分析显然是错误的. 又不是只有分成一边是空的才会达到worst. 一边是一个一边是n-1个行不行? 一边是2个一边是n-2个行不行?
> 有一半总是常数行不行? 有一半个数不断变化但是上界是o(n)的行不行? 太多了.
>
> 2011/3/16 Larry, LIU Xinyu <liuxiny...@gmail.com>
> TopCoder Handle:...
>
> read more >>
Larry, LIU Xinyu
的确不那么严格的给个例子，假设算法每次pivot的分割都很不均匀，例如1:99吧，也就是比pivot大的元素个数是比pivot小的元素个数的
99倍。
令K=100
第一次分割后，xs=as++bs 有length as/length xs = K; 此次运行时间T(n), 是令xs = bs，继续分割；
第二次分割后，仍然as只有1/K的xs长，此次运行时间T(n(K-1)/K), 继续分割；
...
总时间是：T(n)+T(n(K-1)/K)+T(n(K-1)^2/(K^2))+...
注意到K-1/K<1，这个等比数列求和收敛到K。
故复杂度是O(nK)=O(100n)=O(n)
事实上，真正悲剧的情形是K=O(n)。每次左右不对称的比例达到n的量级就退化到O(n^2)了，包括：
左侧0， 右侧n-1
左侧1， 右侧n-2
....
左侧O(1)个，右侧O(n)个
--
LIU
On Mar 16, 3:17 pm, Wu Yin <wyw...@gmail.com> wrote:
> 你再好好想想吧. 这个确实是worst case. 但是这难道是唯一的worst case么? 你只考虑了这种情况发生的概率, 你如何证明
> 只要避免了这种情况, 算法的运行时间就不是O(n^2), 嗯?
>
> 2011/3/16 Larry, LIU Xinyu <liuxiny...@gmail.com>
> ...
>
> read more >>
Wu Yin
Hi,
Wu Yin
Larry, LIU Xinyu
其实说明一个问题：如果算法分为best case, worst case, 和average case。
partition的average case更加接近best case而远离worst case。（又要被批评不严格了）
这也是为什么quick sort在大多数的场合表现很好，而人们存在相对简单的手段避免被某些特殊情况（属于worst case）
exploit。
另：对于99:1的情况，我可以利用master methods直接从T(n)=T(n/K)+T(n(K-1)/K) + cn 直接给出
O(n)，
但是我仍然一步一步列出来，然后用序列求和计算，因为这样比较省力，可以少记忆一些东西。
--
LIU
On Mar 16, 3:47 pm, Wu Yin <wyw...@gmail.com> wrote:
> 你这个例子确实不严格. 不仅不严格, 而且说明不了任何问题. worst case是每次长度减少固定数值,
> 不是减少固定比例。也就是说，是每次从n变成n-k，不是每次从n变成n-n/k。
> 其实我在上面已经说过了。如果每次partition之后总有一个序列的长度是o(n)的，那会如何？注意是o(n)不是O(n)。你这个什么1:XXXX就已经是O(n)量级了，
> 当然能分析出总体O(n)的复杂度。
>
> 2011/3/16 Larry, LIU Xinyu <liuxiny...@gmail.com>
> ...
>
> read more >>
Shuo Chen
On Mar 16, 1:54 pm, Wu Yin <wyw...@gmail.com> wrote:
> 不想再回了,意义不大了.
> 你这个分析显然是错误的. 又不是只有分成一边是空的才会达到worst. 一边是一个一边是n-1个行不行? 一边是2个一边是n-2个行不行?
> 有一半总是常数行不行? 有一半个数不断变化但是上界是o(n)的行不行? 太多了.
>
> 2011/3/16 Larry, LIU Xinyu <liuxiny...@gmail.com>
> TopCoder Handle: ...
>
> read more >>
Larry, LIU Xinyu
我也感觉这么Re来Re去下去不大好了。我贴一段CLRS 7.2.1的一段：
The worst-case behavior for quicksort occurs when the partitioning
routine produces one subproblem with n - 1 elements and one with 0
elements. (This claim is proved in Section 7.4.1.) Let us assume that
this unbalanced partitioning arises in each recursive call. The
partitioning costs Θ(n) time. Since the recursive call on an array of
size 0 just returns, T(0) = Θ(1), and the recurrence for the running
time is
T(n)
=
T(n - 1) + T(0) + Θ(n)
=
T(n - 1) + Θ(n).
On Mar 16, 1:54 pm, Wu Yin <wyw...@gmail.com> wrote:
> 不想再回了,意义不大了.
> 你这个分析显然是错误的. 又不是只有分成一边是空的才会达到worst. 一边是一个一边是n-1个行不行? 一边是2个一边是n-2个行不行?
> 有一半总是常数行不行? 有一半个数不断变化但是上界是o(n)的行不行? 太多了.
>
> 2011/3/16 Larry, LIU Xinyu <liuxiny...@gmail.com>
> TopCoder Handle:...
>
> read more >>
Shuo Chen
Wu Yin 已经说了"worst case是每次长度减少固定数值, 不是减少固定比例"，不是分成 0 vs. n-1 才叫 worst
case。
> ...
>
> read more >>
songyy
我们算法课刚好讲过这个，看这个Lecture Notes的71页以后：
http://www.eusoff.nus.edu.sg/~flyfy1/learn/alg/Lecture7.pdf
On Mar 15, 11:29 am, Devymex <devy...@gmail.com> wrote:
> 任意一个长度为数组，可能有正有负，32位范围为界。
>
> 求O(n)算法，将数组整理为前n/2部分都小于后n/2部分，但各部分不要求有序。
>
> 暂时没有思路。
>
> =========程序控 <http://www.cnblogs.com/devymex>=========
>
> 2011/3/14 Chinainvent <chinainvent....@gmail.com>
>
>
>
> > 很神奇，此刻居然可以轻松地访问google site而不用翻墙，解禁了？
>
> > 2011/3/14 Larry, LIU Xinyu <liuxiny...@gmail.com>
>
> >> 刚刚脱稿：
>
> >>http://sites.google.com/site/algoxy/introduction
> >> (在墙外)
>
> >> --
> >> LIU
>
> > --
> > Chinainvent
> > Blog:http://blog.csdn.net/chinainvent
> > Work at Alibaba <http://www.alibaba.com>- Hide quoted text -
>
> - Show quoted text -
Larry, LIU Xinyu
A self contained Python program with test cases as below.
I considered another method, which is essentially equivalent to nth-
element method:
function nth(xs, k)
l <- 1
u <- length xs
loop
x <- max(xs[1..k])
y <- min(xs[k+1..u])
if x < y then
return
else
swap(x, y)
l <- partition xs[1..k] with x
u <- partition xs[k_1..n] with y
Here are the source code:
----------------8--------------------
#!/usr/bin/python
import random # for test only
# partition xs[l..u] with value x
def partition_with(xs, l, u, x):
left = l
for right in range(l, u+1):
if xs[right] <= x:
(xs[left], xs[right]) = (xs[right], xs[left])
left = left + 1
return left
# Randomized partition with
def partition(xs, l, u):
return partition_with(xs, l, u, xs[random.randint(l, u)])
# method 1, randomized nth-element
def partition_at(xs, k):
(l, u)=(0, len(xs) - 1)
while True:
m = partition(xs, l, u)
if m < k:
l = m
elif m > k:
u = m - 1
else:
return
# method 2, min-max
def partition_at2(xs, k):
(l, u) = (0, len(xs) - 1)
while True:
a = max_at(xs, l, k)
b = min_at(xs, k, u)
if xs[a] > xs[b]:
(xs[a], xs[b]) = (xs[b], xs[a])
(l, u) = (partition_with(xs, l, k-1, xs[a]),
partition_with(xs, k, u, xs[b]) - 1)
else:
return
# find the index of min/max elements from x[l..u]
def max_at(xs, l, u):
i = l
for j in xrange(l, u+1):
if xs[j] > xs[i]:
i = j
return i
def min_at(xs, l, u):
i = l
for j in xrange(l, u+1):
if xs[j] < xs[i]:
i = j
return i
# a brute force verification
def verify(xs, k):
assert(sorted(xs[:k]) == sorted(xs)[:k]):
def gen_xs(n):
xs = random.sample(range(n), random.randint(2, n))
k = random.randint(1, len(xs)-1)
return (xs, k)
def test():
n = 10000
for i in range(100):
(xs, k)=gen_xs(n)
partition_at(xs, k)
verify(xs, k)
(xs, k)=gen_xs(n)
partition_at2(xs, k)
verify(xs, k)
if __name__ == "__main__":
test()
Larry, LIU Xinyu
And a Haskell nth-elem program for reference:
import Data.List -- for partition function
import Test.QuickCheck
-- returns the top n elements
top::Int->[Int]->[Int]
top _ [] = []
top 0 _ = []
top n (x:xs) | len ==n = as
| len < n = as++[x]++(top (n-len-1) bs)
| otherwise = top n as
where
(as, bs) = partition (<= x) xs
len = length as
prop_top :: Int ->[Int] ->Bool
prop_top k xs = if k>=0 then sort (top k xs) == take k (sort xs)
else True
Here is the quick verification:
*> test prop_top
OK, passed 100 tests.
Alternatively, the `partition` can be replaced as:
as = [ a | a<-xs, a<=x]
bs = [ b | b<-xs, b>x]
And here is a median method for change the pivot:
median x3 = sum x3 - maximum x3 - minimum x3
example: median [3, 1, 2] ==> 2
About the min-max method I mentioned in previous post.
The worst case happens when the sequence is in decrease order, and the
algorithm downgrades to O(n^2)
--
LIU