Please help me prove SUM(logi) is Omega(nlogn) - CS版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

CS版 - Please help me prove SUM(logi) is Omega(nlogn)

相关主题
● 求复杂度分析的一个递归式的解	● 请教：K-Nearest neighbor search 有现成算法吗？
● 问一个算法	● 算法题目请教 (转载)
● 【包子求助】20M*20M的loop怎么搞？ (转载)	● 几道算法题求教
● 01背包问题的DP算法复杂度O(nW)，可是为什么还是pseudopolynomial time?	● About testing of uniform distribution
● Transportation problem	● 请教大家一个问题
● Please help, an algorithem question	● 算法疑问
● 一个算法时间复杂度问题	● 请教背包问题。
● [合集] How to sort a singly linked list in O(n) time?	● 问一个链表方面的算法问题

相关话题的讨论汇总
话题: nlogn话题: logn话题: omega话题: sum话题: logi

进入CS版参与讨论

1

(共1页)

m****w 发帖数: 36	1 I can prove it's O(nlogn), like: log1 + log2 + .....+ logn <= logn + logn + .... + logn = nlogn How can it be omega(nlogn)??
m****w 发帖数: 36	2 solution: log nn-1n-2...21 >= log nn-1n-2...n/2>=log n/2n/2....n/2=(n/2) log(n/2) which is Omega(nlogn)
a****1 发帖数: 61	3 sum(logi) >= logn/2 + log(n/2 + 1) + .. + logn >= n/2 * log(n/2) >= 0.5n * logn - 0.5n * log2 当n大到一定 sum(logi) >= Cnlogn 又有sum(logi) < nlogn (显然) 【在 m****w 的大作中提到】 : I can prove it's O(nlogn), like: : log1 + log2 + .....+ logn <= logn + logn + .... + logn = nlogn : How can it be omega(nlogn)??

1

(共1页)

进入CS版参与讨论

相关主题
● 问一个链表方面的算法问题	● Transportation problem
● 询问一个Big O notation的问题	● Please help, an algorithem question
● 求问时间复杂度	● 一个算法时间复杂度问题
● Godel's Lost Paper to Neuman(zz)	● [合集] How to sort a singly linked list in O(n) time?
● 求复杂度分析的一个递归式的解	● 请教：K-Nearest neighbor search 有现成算法吗？
● 问一个算法	● 算法题目请教 (转载)
● 【包子求助】20M*20M的loop怎么搞？ (转载)	● 几道算法题求教
● 01背包问题的DP算法复杂度O(nW)，可是为什么还是pseudopolynomial time?	● About testing of uniform distribution

相关话题的讨论汇总
话题: nlogn话题: logn话题: omega话题: sum话题: logi

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)