2007年01月09日 星期二 17:49
On 1/9/07, heyuqi <yuqi.he在gmail.com> wrote: > > > 其次,堆排的时间复杂度是O(nlogn)没有错,但是,取前10个的时间复杂度并不是O(10logn) > > 而应该是O(n),确切的说大概是O((n-10)*log(10)),注:所有log均以2为底 > > 不对吧,若一个数组 array[n] 是堆,从中删除一个数据,并使用后来的 array[n-1]仍是堆,这种算法的时候复杂度为 O(logn) > > 这是我们课后练习的一道题,以前证过,现在一时想不起了。只能把结果写出来 > 你的前提是array已经是一个堆了。但现在的情况程序里没有堆啊。 如果先用堆排把所有数都排一遍,那不又是一个O(nlogn)吗? 而我说的是从一个无序的数组中取前10个最大的元素的复杂度是O(n) -- Best Regards, Leo Jay
2007年01月09日 星期二 17:57
On 1/9/07, Leo Jay <python.leojay at gmail.com> wrote: > > > 你的前提是array已经是一个堆了。但现在的情况程序里没有堆啊。 > 如果先用堆排把所有数都排一遍,那不又是一个O(nlogn)吗? 从堆中删除一个数据,剩下来的就不是堆了,还要重排一次。 而我说的是从一个无序的数组中取前10个最大的元素的复杂度是O(n) 能给个例子我看看吗?我想不到如何实现。 -------------- next part -------------- An HTML attachment was scrubbed... URL: http://python.cn/pipermail/python-chinese/attachments/20070109/b64994a3/attachment.htm
2007年01月09日 星期二 19:41
On 1/9/07, heyuqi <yuqi.he在gmail.com> wrote: > On 1/9/07, Leo Jay <python.leojay在gmail.com> wrote: > > > > 你的前提是array已经是一个堆了。但现在的情况程序里没有堆啊。 > > 如果先用堆排把所有数都排一遍,那不又是一个O(nlogn)吗? > > 从堆中删除一个数据,剩下来的就不是堆了,还要重排一次。 > > > 而我说的是从一个无序的数组中取前10个最大的元素的复杂度是O(n) > > 能给个例子我看看吗?我想不到如何实现。 > 堆化的复杂度就是O(n)啊,如果堆化完了之后再全部排序就是O(nlogn), 如果不全部排序,只取前10个,那复杂度还是O(n)啊。不会是O(log(n))的 -- Best Regards, Leo Jay
2007年01月09日 星期二 20:34
建堆怎么可能O(n)?你写个程序自己跑跑看就知道了,O(nlogn)。理论上讲, log1+log2+...+logn=O(nlogn) 这个问题有特殊性,因为楼主只要10个最大的,所以整个堆只要保留上面10层就可以了。于是用堆方法可以降到O(n),但常系数约在20-30,远超过半个快速排序的3。 2007/1/9, Leo Jay <python.leojay在gmail.com>: > 堆化的复杂度就是O(n)啊,如果堆化完了之后再全部排序就是O(nlogn), > 如果不全部排序,只取前10个,那复杂度还是O(n)啊。不会是O(log(n))的
2007年01月09日 星期二 20:47
令f(A,k)计算A中前k大的元素。 随便挑一个元素x,可以在O(|A|)时间里把A分成两部分B和C,其中B中元素都严格比x大,而C中元素都小于等于x。 如果|B|=k,B就是我们所求的,stop; 如果k<|B|,递归 f(B,k); 如果k>|B|,首先B是我们所求的一部分,然后递归f(C,k-|B|)。 严格的分析时间复杂度比较麻烦,粗略地讲,期望上|B|=|C|=0.5|A|,所以期望时间复杂度约为|A|+0.5|A|+0.25|A|+...这是个简单的等比数列求和问题,解是2|A|。刚才我说了,这个计算很粗略,很不严格。精确的期望值大约在3|A|左右。 在 07-1-9,heyuqi<yuqi.he在gmail.com> 写道: > 半个快速排序?可以实现需求吗? > > 在我这里快速排序也叫分划排序,每一趟排序都确定一个数的位置,使它左边的数都小于它,右边的数都大于它。而一趟排序的时间复杂度应该是 > O(n),每个数都要扫描一遍。 >
2007年01月09日 星期二 21:12
On 1/9/07, Yunfeng Tao <taoyfeng在gmail.com> wrote: > 建堆怎么可能O(n)?你写个程序自己跑跑看就知道了,O(nlogn)。理论上讲, > log1+log2+...+logn=O(nlogn) > 这个问题有特殊性,因为楼主只要10个最大的,所以整个堆只要保留上面10层就可以了。于是用堆方法可以降到O(n),但常系数约在20-30,远超过半个快速排序的3。 > 理论的东西怎么可能是写个程序跑跑看就能看出结果的? 你可以看看<> 6.4章的Building a heap. 里面写得很清楚, the running time of BUILD-MAX-HEAP can be bounded as O(n) -- Best Regards, Leo Jay
2007年01月09日 星期二 22:21
On 1/9/07, Leo Jay <python.leojay at gmail.com> wrote: > > On 1/9/07, heyuqi <yuqi.he at gmail.com> wrote: > > On 1/9/07, Leo Jay <python.leojay at gmail.com> wrote: > > > > > > 你的前提是array已经是一个堆了。但现在的情况程序里没有堆啊。 > > > 如果先用堆排把所有数都排一遍,那不又是一个O(nlogn)吗? > > > > 从堆中删除一个数据,剩下来的就不是堆了,还要重排一次。 > > > > > 而我说的是从一个无序的数组中取前10个最大的元素的复杂度是O(n) > > > > 能给个例子我看看吗?我想不到如何实现。 > > > > 堆化的复杂度就是O(n)啊,如果堆化完了之后再全部排序就是O(nlogn), > 如果不全部排序,只取前10个,那复杂度还是O(n)啊。不会是O(log(n))的 :P 现在是晕头了,把前面的也忘掉了 to Yunfeng Tao,O(n) 应该是这样来的: i:1->n/2 累加 log(n/i) = 取整(n/2) * logn - log( 取整( n/2 )! ) 由一个叫 Stirling 公式知上式 = O( n ) 不过 Stirling 公式是什么就不知道 ;-) On 1/9/07, Yunfeng Tao <taoyfeng at gmail.com> wrote: > > 令f(A,k)计算A中前k大的元素。 > 随便挑一个元素x,可以在O(|A|)时间里把A分成两部分B和C,其中B中元素都严格比x大,而C中元素都小于等于x。 晕,你这里假充的数据都已经是有序了,这种情况使用快速排序会有最坏的时间复杂度的! 你说随便挑一个元素 x,但是在没有进行过排序的数据中,你是无法保证 B 中元素一定比 x 大,C 中元素一定小于等于 x 的。 要针对 x 进行过一趟快速排序,这时候 x 所处的位子才是你假充的情况。x 才是用来分割 B & C 的。 这种方法是有序表查找的方法,类似二分查找和 Fibonacci 查找 -------------- next part -------------- An HTML attachment was scrubbed... URL: http://python.cn/pipermail/python-chinese/attachments/20070109/d060d87b/attachment.html
2007年01月10日 星期三 09:26
On 1/4/07, daifei <bonycamel at gmail.com> wrote: > > > > > > 各位好,我要实现以下需求,感觉python可能有现成的方法,请各位指教。 > > > > 在一个list中,有大量整数(10000个或更多),例如:[1,1,3,3,9999,9,3,512,1,8,9,……] > > 我需要写一个算法,统计这个数字list中出现次数最多的10个整数,分别存到变量i1-i10。 > > > > 用一般的循环应该可以实现,但是效率比较差,也比较麻烦,请问python有什么现成的实现方式吗?谢谢。 > 不用循环用什么呢? -- GoogleTalk: qcxhome at gmail.com MSN: qcxhome at hotmail.com My Space: tkdchen.spaces.live.com BOINC: boinc.berkeley.edu 中国分布式计算总站: www.equn.com
2007年01月10日 星期三 09:56
"假充"?什么东西? 注意,我挑的是一个元素,不是一个位置。再去温习下快速排序吧。 在 07-1-9,heyuqi<yuqi.he在gmail.com> 写道: > On 1/9/07, Yunfeng Tao <taoyfeng在gmail.com> wrote: > > 令f(A,k)计算A中前k大的元素。 > > 随便挑一个元素x,可以在O(|A|)时间里把A分成两部分B和C,其中B中元素都严格比x大,而C中元素都小于等于x。 > > 晕,你这里假充的数据都已经是有序了,这种情况使用快速排序会有最坏的时间复杂度的! > > 你说随便挑一个元素 x,但是在没有进行过排序的数据中,你是无法保证 B 中元素一定比 x 大,C 中元素一定小于等于 x 的。 > > 要针对 x 进行过一趟快速排序,这时候 x 所处的位子才是你假充的情况。x 才是用来分割 B & C 的。 > > 这种方法是有序表查找的方法,类似二分查找和 Fibonacci 查找 >
2007年01月10日 星期三 10:57
On 1/9/07, Yunfeng Tao <taoyfeng在gmail.com> wrote: > 令f(A,k)计算A中前k大的元素。 > 随便挑一个元素x,可以在O(|A|)时间里把A分成两部分B和C,其中B中元素都严格比x大,而C中元素都小于等于x。 > 如果|B|=k,B就是我们所求的,stop; > 如果k<|B|,递归 f(B,k); > 如果k>|B|,首先B是我们所求的一部分,然后递归f(C,k-|B|)。 > 严格的分析时间复杂度比较麻烦,粗略地讲,期望上|B|=|C|=0.5|A|,所以期望时间复杂度约为|A|+0.5|A|+0.25|A|+...这是个简单的等比数列求和问题,解是2|A|。刚才我说了,这个计算很粗略,很不严格。精确的期望值大约在3|A|左右。 > 你用了类似快排的思路,所以会有跟快排一样的缺陷:最差情况的复杂度是O(n^2) 想像一下你第一次选中的是最小的数,第二次选中的是第二小的数,... 第i次选中第i小的数。 很明显的O(n^2) 楼主的应用,还是做个堆,然后取10个最大的数,这样复杂度比较有保证,O(n)。 -- Best Regards, Leo Jay
2007年01月10日 星期三 11:08
这个是我记错了,确实是O(n) 2007/1/9, Leo Jay <python.leojay在gmail.com>: > On 1/9/07, Yunfeng Tao <taoyfeng在gmail.com> wrote: > > 建堆怎么可能O(n)?你写个程序自己跑跑看就知道了,O(nlogn)。理论上讲, > > log1+log2+...+logn=O(nlogn) > > 这个问题有特殊性,因为楼主只要10个最大的,所以整个堆只要保留上面10层就可以了。于是用堆方法可以降到O(n),但常系数约在20-30,远超过半个快速排序的3。 > > > > > 理论的东西怎么可能是写个程序跑跑看就能看出结果的? > > 你可以看看<> 6.4章的Building a heap. > 里面写得很清楚, > the running time of BUILD-MAX-HEAP can be bounded as O(n) > > > -- > Best Regards, > Leo Jay > _______________________________________________ > python-chinese > Post: send python-chinese在lists.python.cn > Subscribe: send subscribe to python-chinese-request在lists.python.cn > Unsubscribe: send unsubscribe to python-chinese-request在lists.python.cn > Detail Info: http://python.cn/mailman/listinfo/python-chinese
2007年01月10日 星期三 11:38
不错,最坏情况是O(n^2)。学界有大量的工作投入到如何不让快排的最坏情况出现,比较简单的方法是:随机选择元素x。 快排有许多非常好的优点:第一它快,期望时间复杂度O(nlogn),O(n^2)的情况几乎不会出现,而且常数非常小;第二它容易实现,不容易写错。所以很多语言(比如C)的类库提供的排序方法还是快排。 2007/1/10, Leo Jay <python.leojay在gmail.com>: > On 1/9/07, Yunfeng Tao <taoyfeng在gmail.com> wrote: > > 令f(A,k)计算A中前k大的元素。 > > 随便挑一个元素x,可以在O(|A|)时间里把A分成两部分B和C,其中B中元素都严格比x大,而C中元素都小于等于x。 > > 如果|B|=k,B就是我们所求的,stop; > > 如果k<|B|,递归 f(B,k); > > 如果k>|B|,首先B是我们所求的一部分,然后递归f(C,k-|B|)。 > > 严格的分析时间复杂度比较麻烦,粗略地讲,期望上|B|=|C|=0.5|A|,所以期望时间复杂度约为|A|+0.5|A|+0.25|A|+...这是个简单的等比数列求和问题,解是2|A|。刚才我说了,这个计算很粗略,很不严格。精确的期望值大约在3|A|左右。 > > > > 你用了类似快排的思路,所以会有跟快排一样的缺陷:最差情况的复杂度是O(n^2) > 想像一下你第一次选中的是最小的数,第二次选中的是第二小的数,... 第i次选中第i小的数。 > 很明显的O(n^2) > > 楼主的应用,还是做个堆,然后取10个最大的数,这样复杂度比较有保证,O(n)。 > > -- > Best Regards, > Leo Jay > _______________________________________________ > python-chinese > Post: send python-chinese在lists.python.cn > Subscribe: send subscribe to python-chinese-request在lists.python.cn > Unsubscribe: send unsubscribe to python-chinese-request在lists.python.cn > Detail Info: http://python.cn/mailman/listinfo/python-chinese
2007年01月10日 星期三 20:56
On 1/10/07, Yunfeng Tao <taoyfeng at gmail.com> wrote: > > 不错,最坏情况是O(n^2)。学界有大量的工作投入到如何不让快排的最坏情况出现,比较简单的方法是:随机选择元素x。 > > 快排有许多非常好的优点:第一它快,期望时间复杂度O(nlogn),O(n^2)的情况几乎不会出现,而且常数非常小;第二它容易实现,不容易写错。所以很多语言(比如C)的类库提供的排序方法还是快排。 试着写了一个完整的实现,包括堆和"半快排"两种算法。 几点想法: 1. 算法的前半部分(计算elements),感觉还是 d[x] = d.get(x, 0) + 1 的方法最好,简洁且高效 2. 本来想自己写一个堆的,不过发现标准库中的heapq已经实现的很漂亮了,就偷懒直接用了。 3. 快排的实现比想象中麻烦,我调了不少时间。主要是这里partition函数的实现需要特别注意,某些写法对于单纯的排序没有问题,但在这个场景下就会出错(比如遇到重复元素时会导致死循坏)。 4. 时间复杂度和大家讨论的结果一样,怎么写都是O(n),区别只在常数上。 5. 因为heapq有c的实现,所以直接比较的话堆方法速度肯定比纯python的半快排方法要快,不过这并不说明堆的算法常数上更优。详细的测试我还没做。 6. 感觉python写这种基础的算法优势不大,因为效率方面的顾虑很多pythonic的写法都用不上,感觉和写c区别不大。当然也可能只是我功力还不够... 代码如下: import heapq import random class Element(object): def __init__(self, key, value): self.key = key self.value = value # override __cmp__ method so that we can implement generally klargest method def __cmp__(self, other): return self.key.__cmp__(other.key) def __repr__(self): return (self.key, self.value).__repr__() def klargest_by_heap(array, k): heapq.heapify(array) return heapq.nlargest(k, array) def partition(array, start, end): pivot_index = random.randint(start, end) array[start], array[pivot_index] = array[pivot_index], array[start] i, j = start, end while True: while i <= j and array[i] >= array[start]: i += 1 while i <= j and array[j] < array[start]: j -= 1 if i > j: break array[i], array[j] = array[j], array[i] pivot_index = i - 1 # can be ignored in normal quicksort, but MUST do it in this case array[pivot_index], array[start] = array[start], array[pivot_index] return pivot_index def klargest_by_quicksort(array, k): start, end, split = 0, len(array) - 1, len(array) - 1 while split != k - 1: split = partition(array, start, end) if split < k - 1: start = split + 1 elif split > k - 1: end = split - 1 return array[:k] def k_most_frequently(array, k): d = {} for x in array: d[x] = d.get(x,0) + 1 elements = [Element(count, value) for (value, count) in d.items()] return [e.value for e in klargest(elements, k)] if __name__ == "__main__": a = [1,5,4,4,2,2,4] klargest = klargest_by_heap print k_most_frequently(a, 2) klargest = klargest_by_quicksort print k_most_frequently(a, 2) -------------- next part -------------- An HTML attachment was scrubbed... URL: http://python.cn/pipermail/python-chinese/attachments/20070110/01721d72/attachment.htm
2007年01月11日 星期四 09:58
在 07-1-10,swordsp<sparas2006在gmail.com> 写道: > > 3. > 快排的实现比想象中麻烦,我调了不少时间。主要是这里partition函数的实现需要特别注意,某些写法对于单纯的排序没有问题,但在这个场景下就会出错(比如遇到重复元素时会导致死循坏)。 这点我也疏忽了。
2007年01月13日 星期六 16:24
partition的实现有效率问题。如果整个array的元素全同,那么一次partition只能减少一个元素。我稍作修改如下: def partition(array, start, end): pivot_index = random.randint(start, end) array[start], array[pivot_index] = array[pivot_index], array[start] i, j = start+1, end while i <= j: array[i], array[j] = array[j], array[i] while i <= j and array[i]+random.random()-0.5 >= array[start]: i += 1 while i <= j and array[j]+random.random()-0.5 < array[start]: j -= 1 pivot_index = i - 1 array[start], array[pivot_index] = array[pivot_index], array[start] return pivot_index 1.对于整数a,b,如果a
b,那么"a>b+0.5,当且仅当,a>b-0.5,当且仅当,a>b"。根据这个性质,partition结束时,比array[pivot_index]大的都在pivot_index前面,小的都在后面。 2. 和array[pivot_index]等大的元素,每一个都独立地有一半概率排在前面。所以partition结束时,和array[pivot_index]等大的元素期望上有一半排在pivot_index前面。 如此一来,到达期望上的二分,避免最坏情况的出现。 在 07-1-10,swordsp<sparas2006在gmail.com> 写道: > > 试着写了一个完整的实现,包括堆和"半快排"两种算法。 > 几点想法: > 1. 算法的前半部分(计算elements),感觉还是 d[x] = d.get(x, 0) + 1 的方法最好,简洁且高效 > 2. 本来想自己写一个堆的,不过发现标准库中的heapq已经实现的很漂亮了,就偷懒直接用了。 > 3. > 快排的实现比想象中麻烦,我调了不少时间。主要是这里partition函数的实现需要特别注意,某些写法对于单纯的排序没有问题,但在这个场景下就会出错(比如遇到重复元素时会导致死循坏)。 > 4. 时间复杂度和大家讨论的结果一样,怎么写都是O(n),区别只在常数上。 > 5. > 因为heapq有c的实现,所以直接比较的话堆方法速度肯定比纯python的半快排方法要快,不过这并不说明堆的算法常数上更优。详细的测试我还没做。 > 6. > 感觉python写这种基础的算法优势不大,因为效率方面的顾虑很多pythonic的写法都用不上,感觉和写c区别不大。当然也可能只是我功力还不够... > > 代码如下: > > import heapq > import random > > class Element(object): > > def __init__(self, key, value): > self.key = key > self.value = value > > # override __cmp__ method so that we can implement generally klargest > method > def __cmp__(self, other): > return self.key.__cmp__(other.key) > > def __repr__(self): > return (self.key, self.value).__repr__() > > def klargest_by_heap(array, k): > heapq.heapify(array) > return heapq.nlargest(k, array) > > def partition(array, start, end): > pivot_index = random.randint(start, end) > array[start], array[pivot_index] = array[pivot_index], array[start] > i, j = start, end > while True: > while i <= j and array[i] >= array[start]: > i += 1 > while i <= j and array[j] < array[start]: > j -= 1 > if i > j: > break > array[i], array[j] = array[j], array[i] > pivot_index = i - 1 > > # can be ignored in normal quicksort, but MUST do it in this case > array[pivot_index], array[start] = array[start], array[pivot_index] > > return pivot_index > > def klargest_by_quicksort(array, k): > start, end, split = 0, len(array) - 1, len(array) - 1 > while split != k - 1: > split = partition(array, start, end) > if split < k - 1: > start = split + 1 > elif split > k - 1: > end = split - 1 > return array[:k] > > def k_most_frequently(array, k): > d = {} > for x in array: > d[x] = d.get(x,0) + 1 > elements = [Element(count, value) for (value, count) in d.items()] > return [e.value for e in klargest(elements, k)] > > if __name__ == "__main__": > a = [1,5,4,4,2,2,4] > > klargest = klargest_by_heap > print k_most_frequently(a, 2) > > klargest = klargest_by_quicksort > print k_most_frequently(a, 2) > > _______________________________________________ > python-chinese > Post: send python-chinese在lists.python.cn > Subscribe: send subscribe to > python-chinese-request在lists.python.cn > Unsubscribe: send unsubscribe to > python-chinese-request在lists.python.cn > Detail Info: > http://python.cn/mailman/listinfo/python-chinese >
Zeuux © 2025
京ICP备05028076号