m****w
发帖数: 36 | 1 【 以下文字转载自 CS 讨论区 】
发信人: MadCow (Very Mad), 信区: CS
标 题: Please help me prove SUM(logi) is Omega(nlogn)
发信站: BBS 未名空间站 (Wed Mar 12 19:31:53 2008)
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 I can prove it's O(nlogn), like:
log1 + log2 + .....+ logn <= logn + logn + .... + logn = nlogn
How can it be omega(nlogn)?? |
|
g*********s
发帖数: 1782 | 3 【 以下文字转载自 JobHunting 讨论区 】
发信人: gandjmitbbs (Nothing), 信区: JobHunting
标 题: O(NlogN) largest rectangle in histogram
发信站: BBS 未名空间站 (Sun Dec 12 18:52:53 2010, 美东)
I'm not talking about the O(N) dp solution, but the O(NlogN) one based on
the order-statistic tree here:
http://blog.csdn.net/arbuckle/archive/2006/05/06/710988.aspx |
|
r********7
发帖数: 42 | 4 比方说：0，2，0，4，3，1，5，0 =〉0，2，3，5
我的解法是sort this sequence X to Y, Get the LCS of X and Y.
Time = O(nlogn + n^2) = O(N^2)
对方说还能更快。谁知道该怎么改进？
Updated: 我忘了说了，是求*最长*单调上升子列 |
|
p*********a
发帖数: 21 | 5 用数列d[]维护一个单调上升序列. 每读取一个新的数后，如果f[len]
中, len++; 否则找到某个i使得x>d[i]且x<=d[i+1]，用x去更新f[i+1]；最后看d数列
有多长就行了。
d单增，所以每次查找索引i时可以用二分查找，因此时间复杂度为O(nlogn)。
举个例子，假如序列为 2 5 3 4, 则d数列如下
2
2 5
2 3
2 3 4
最后，d的长度为3，LIS is 3。
不过，最后的d不一定是最长上升子序列的答案。 |
|
j*********h
发帖数: 21 | 6 1. number all the element in the original array, in growing sequence (O(n)).
e.g. original array is [3,2,1,0,1,2], after numbering, it became [(3,0),
(2,1),(1,2),(0,3),(1,4),(2,5)].
the "number" of each element is the corresponding position it is in the
original array.
2. after numbering, sort the new array according to their original value ,
using quicksort. (O(nlogn))
e.g. after sorting, [3,2,1,0,1,2]->[0,1,1,2,2,3]. ( I didn't list the "
position" of each element here).
3. find the lo |
|
d****j
发帖数: 293 | 7 ...这道题是非常经典的算法题了，网上讨论的有很多，大家应该记住（我也忘了，貌似2年前看到的了）。google: "nlogn的最长子序列算法"
我把答案和分析zz到这里吧(具体的代码网上自己搜):
这是一个很好的题目。题目的算法还是比较容易看出来的，就是求最长上升子序列的长
度。不过这一题的数据规模最大可以达到40000，经典的O(n^2)的动态规划算法明显会
超时。我们需要寻找更好的方法来解决是最长上升子序列问题。
先回顾经典的O(n^2)的动态规划算法，设A[i]表示序列中的第i个数，F[i]表示从1
到i这一段中以i结尾的最长上升子序列的长度，初始时设F[i] = 0(i = 1, 2, ...,
len(A))。则有动态规划方程：F[i] = max{1, F[j] + 1} (j = 1, 2, ..., i - 1, 且
A[j] < A[i])。
现在，我们仔细考虑计算F[i]时的情况。假设有两个元素A[x]和A[y]，满足
(1)x < y < I (2)A[x] < A[y] < A[i] (3)F[x] = F[y]
此时，选择F[x]和选择F[y]都可以得到 |
|
m*****n
发帖数: 5245 | 8 ☆─────────────────────────────────────☆
rentny2007 (rent) 于 (Sun Oct 25 15:15:53 2009, 美东) 提到:
比方说：0，2，0，4，3，1，5，0 =〉0，2，3，5
我的解法是sort this sequence X to Y, Get the LCS of X and Y.
Time = O(nlogn + n^2) = O(N^2)
对方说还能更快。谁知道该怎么改进？
Updated: 我忘了说了，是求*最长*单调上升子列
☆─────────────────────────────────────☆
algorithmics (沙盘推演) 于 (Sun Oct 25 15:19:28 2009, 美东) 提到:
求两个序列的LCS, 如果你知道其中有一个是单调的, 就能在linear时间中找到.
☆─────────────────────────────────────☆
rentny2007 (rent) 于 (Sun Oct 25 15:26:05 2009, 美 |
|
j******4
发帖数: 116 | 9 关于这个贴 ： http://www.mitbbs.com/article_t/JobHunting/31648139.html
dingzj 在最后给拉一个分析， 但是对于D[]的生成还是不太理解。有没有人做过这道
题？
比如这个例子, 我的理解是：
A = {1, 7, 5, 0， 8, 9}
step1:
D = 1
step 2:
D =1, 7
step 3:
D = 1, 5 ?? 这里用5 代替啦 7， 对吗？
step 4:
D = 0, 5 ?? 同样， 用0带替 1？
step 5:
D = 0, 5, 8
step 6:
D = 0, 5, 8, 9
dingzj (Jason) 于 (Tue Mar 2 01:14:48 2010, 美东) 提到:
...这道题是非常经典的算法题了，网上讨论的有很多，大家应该记住（我也忘了，貌
似2年前看到的了）。google: "nlogn的最长子序列算法"
我把答案和分析zz到这里吧(具体的代码网上自己搜):
这是一个很好的题目。题目的算法还是比较容易看出来的，就是求最长上升子序列的长
度。不过这一题的数据 |
|
|
b*****e
发帖数: 474 | 11 我来抛砖吧。
O(n) 的解法大家都知道了吧。这个是O(n log n)的，比较直观点，
就是简单的Divide & Conquer，分别计算前半和后半的最大矩形面积，
然后和贯穿中间的最大矩形比较面积。我用最普通的前后扫描方法
来确定贯穿中间的最大矩形面积（O(n)时间）。所以这个算法和
MergeSort的情形一样，都是分成两个一半大小的子问题，然后O(n)
时间来合成。所以是O(nlogn)。
Java 程序：
public class histo {
public static int maxRect(int[] table ) {
return maxRect(table, 0, table.length-1);
}
public static int maxRect(int[] table, int start, int end) {
if ( start == end ) return table[start];
if ( start == end-1)
return Math.max(Math.max(ta... 阅读全帖 |
|
l***i
发帖数: 1309 | 12 Although in practice O(n)-median algorithm carries a large constant so will
likely defeat the small constant advantage of quick-sort compared to other O
(nlogn) sorting algorithms. |
|
g*****i
发帖数: 2162 | 13 Wikipedia只给出了O(n)的算法reference,这个估计interview也写不出来.
谁能给个容易写的nlogn算法? 谢谢. |
|
a********1
发帖数: 750 | 14 主要是要用step＊2比较suffix
直接qsort 的复杂度是n^2 logn ， 因为sorting nlogn, 每个compare是n |
|
a********1
发帖数: 750 | 15 嗯，，不过lz的问题是nlogn的构造
感觉快的string算法的基本思想都差不多，就是把已知的比较结果发挥到极限。 |
|
s*w
发帖数: 729 | 16 先 O(nlogn) 找 convex hull (graham scan), 然后 O(n) 找 顶点间最大距离 (
rotating calipers) |
|
l**********r
发帖数: 7 | 17 一道很简单的面试题：
给一个数组arr[]，数组第i个元素表示圆心坐标为(0,i)，半径为arr[i]的圆。求出该
数组里有多少个圆心不同但intersect的圆？
题目很简单，但是小弟只能答出简单的解法，用两个循环一个个找，想不出time
complexity是O(nlogn)的解法。
求各位高手给个思路。 |
|
p********n
发帖数: 165 | 18 对于每个圆 i， 和它的半径r[i]=arr[i], 我们可以考虑这个圆和x-轴的左右两个交点
［start_i, end_i］, 其中start_i = i - array[i] and end_i = i+ array[i];
我们先将所有的圆，按照start_i 排序，然后一个一个的加入， 这个题是要求出，每
次加入一个圆i，有多少个圆k (0 <=k < i) 和第i个圆相交。实质上就是说每加入一个
［start_i, end_i］ 有多少个 [start_k, end_k] ( 0 <= k < i) 和 ［start_i,
end_i］ 相交，然后对 （i = 0...n) 求和就好。
我们按照start index排序，如果 k < i 也就是 start_k < start_i, 那么两个圆［
start_k, end_k］和 ［start_i, end_i］相交的判定条件是 start_i
. 那么这个题就是要用binary search （或者用BST来实现）找到每个 圆［start_i,
end_i］加入的时侯 (1) e... 阅读全帖 |
|
|
s*******m
发帖数: 52 | 20 一般来说2sum 直接排序，然后2pointer, nlogn 的时间
或者是hashmap， O(n) 的时间
题目变成这样， 比如我给 （2，2，2）， target = 4，
我要输出所有可能的index， 也就是 {0，1}， {0，2} ， {1，2}
想了下，是用HashMap 存一个index list的话。遍历每个元素是O(N)，找到解了，打印
list中每个元素要O(n), 一共是n平方。
如果用2 pointer，似乎也没办法O(n)
各位大神有没有啥想法？ |
|
发帖数: 1 | 21 n^2的解法很直接。
还有个nlogn的解法，尼玛就是要死记硬背。
大家怎么看？ |
|
|
|
H**********5
发帖数: 2012 | 24 刚看了下Roy的视频，nlogn实现总算是弄懂了。 |
|
m****w
发帖数: 36 | 25 solution:
log n*n-1*n-2*...*2*1 >= log n*n-1*n-2*...*n/2>=log n/2*n/2*....*n/2=(n/2)
log(n/2)
which is Omega(nlogn) |
|
a****1
发帖数: 61 | 26 sum(logi) >= logn/2 + log(n/2 + 1) + .. + logn
>= n/2 * log(n/2) >= 0.5n * logn - 0.5n * log2
当n大到一定 sum(logi) >= C*n*logn
又有sum(logi) < nlogn (显然) |
|
S*******C
发帖数: 822 | 27 我这里有一个求最长递增子序列长度的O(nlogn)动态规划算法作为参考
public class LongestIncreasingSubseq {
static int min_last_element[];// 记录长度为i的递增子序列中最大元素的最小
值, min_last_element is an sorted array
static int lengthOfLIS;
public static void main(String args[]) {
int a1[] = new int[] { 12, 11, 13, 10, 14, 11, 15, 12, 17, 20, 11,
22 };
min_last_element= new int[a1.length];
System.out.println(findLongestIncreasingSubseq(a1, a1.length));
}
// 返回min_last_element[i]中刚刚大于x的那个元素的下标
sta... 阅读全帖 |
|
o******y
发帖数: 446 | 28 1log1+2log2+...+NlogN > N/2*logN/2 + .... + NlogN > N/2 * N/2 * log N/2
1log1+2log2+...+NlogN < N*NlogN
而 N/2 * N/2 * log N/2 与 N*NlogN 无本质区别。 所以是 N*NlogN |
|
s********k
发帖数: 6180 | 29 我看到很多地方用这样的表示：k1+k2*O(NlogN),这样的表示和k1+k2*NlogN有什么区别
吗？还是说后者更精确？而用big O表示的是上限？quick sort里面的O(NlogN)是否也
能表示成为NlogN?另外像你例子里面的1.326N，能表示成为O(1.326N)吗？谢谢 |
|
x***y
发帖数: 633 | 30 put one copy of the array after the other, and use O(nlogn) LIS and of the
result, find the longest subsequence that does not overlap with itself in original array O(nlogn) with binary search...So, totaly time is O(nlogn)... |
|
B*****t
发帖数: 335 | 31 find the longest subsequence that does not overlap with itself in
original array
这是什么意思？怎么find？O(nlogn)的方法不能直接拿过来用。二分的时候你要维护一
个数列的值，但是你怎么知道哪些需要更新，哪些不要？而且队列组成了一个环，二分被
更新掉的数据在后边可能会用到，你怎么把它恢复？
and of the
itself in original array O(nlogn) with binary search...So, totaly
time is O(nlogn)... |
|
f****4
发帖数: 1359 | 32 那最差的情况，为啥是nlogn？
能详细解释一下么？ 还有，这个是O(nlogn)还是，就是nlogn? |
|
y*********e
发帖数: 518 | 33 第一题，什么情况下favor O(n^2) over O(nlogn)
得考虑常数因子阿，比如，一个是O(n^2)但是其实是2n^2，另外一个是O(nlogn)但是是
44nlog(n)。当n比较小的时候，O(n^2)就比O(nlogn)要快了。 |
|
x**y
发帖数: 70 | 34 好像你的方法不是正解. 我当时的解法, INTERVIEWER 没说错, 只是让我分析O(). 当时
under pressure, 心想比N^2好的, 只能是 nlogn. 现在想想, 那我得证明 average
case: nlogn + n/2log(n/2) + n/4log(n/4) + ... + 1 ==> O(nlogn).
按理说, 电面题应该不是太难, 有牛牛知道这题标准解法吗?
multiply |
|
b********h
发帖数: 119 | 35 应该可以做到O（nlogn）吧。
1. 对所有inverval以起始时间排序 -> nlogn
2. 对每一个inverval，以他的结束时间在他后面所有的interval里binary search。找
到的那个interval前面的所有interval与其conflict。 -> nlogn |
|
n*******n
发帖数: 3 | 36 我来试着证明一下本题的时间复杂度是有下限的。而且下限是 O(nlogk)， n为所有
integer的个数. 证明如下：
一般常识是sort n个integer最快是O(nlogn). 所以把n个integer分成k组，每组分别
sort，再合起来，不可能比O(nlogn)更快。 n ＝ k * m
分别sort k 个 size 为 m的数组共需时间 k * O(mlogm) = O(nlogm). 所以merge k个
数组的时间不可能小于 O（nlogn）- O(nlogm) = O(nlog(n/m)) = O(nlogk) .
楼上各位已经找到最优解了。 |
|
a*******6
发帖数: 520 | 37 所谓的quicksort不stable不是说partition那一步，而是选pivot那步
一般认为的quicksort，（递归的）每次随机选一个pivot，然后partition，复杂度期
望下是O(nlogn)，最坏是O(n^2)，这个可能是你说的不stable
但是partition那一步肯定是O(n)的
理想情况下，如果pivot选到median，那么复杂度肯定是O(nlogn)了
有一种确定性算法可以每次以O(n)的时间选到一个pivot在median附近（至少1/3的元素
小于他，同时至少1/3的元素大于他），那么这样quicksort的复杂度最坏情况下也是O(
nlogn)了，不过实际中没太多人用这个版本，因为其实实际的performance不如那个随
机选pivot的版本 |
|
g*********e
发帖数: 14401 | 38 假设总体interval的范围是[A,B]
1.所有interval按照ai排序 (nlogn)
2.count the number of intervals that intersect (A+B)/2 O(n)
3.recursively do 1 & 2 for F(A,(A+B)/2), F((A+B)/2, B), update the maximun
intersect count
4.base case是一个区间里没有完整的一个interval
跟merge sort差不多思路
time complexity
f(n)=2*f(n/2)+O(n)
根据master theorem 总体时间nlogn
故总体时间还是nlogn |
|
g*********e
发帖数: 14401 | 39 假设总体interval的范围是[A,B]
1.所有interval按照ai排序 (nlogn)
2.count the number of intervals that intersect (A+B)/2 O(n)
3.recursively do 1 & 2 for F(A,(A+B)/2), F((A+B)/2, B), update the maximun
intersect count
4.base case是一个区间里没有完整的一个interval
跟merge sort差不多思路
time complexity
f(n)=2*f(n/2)+O(n)
根据master theorem 总体时间nlogn
故总体时间还是nlogn |
|
f*****e
发帖数: 2992 | 40 复杂度:
没有，每次pop minheap and maxheap and insert minheap and maxheap操作耗时log(
n)，每次operation，至少有一个数组的size要减半，如果每个数组的size都是n，把一
个数组削的只剩一个要log(n)，然后有n个数组，所以nlogn。nlogn * logn = nlogn^2
medi
目的
常大
的k |
|
f******t
发帖数: 18 | 41 咦，kmp估計是正解，感覺還有個nlogn的算法好像也還將就。
掃一遍字符串統計各字符出現次數，得到一個stat[]數組
如果只有一種字符而字符串長度大於一，return true
else
求stat所有值的最大公約數(nlogn)，假設為gcd
if gcd==1，return false
否則，如果存在一種重複T構造S的方法的話，gcd一定是K的因子
而無論K等於gcd的多少倍，S能分成K份就一定能分成gcd份（因為gcd
只能是K的因子）
然後檢測K=gcd，S是否符合要求，符合返回true，否則return false（O(n))
實際上上面的的nlogn複雜度遠遠達不到的~~仔細分析也許會跟kmp的正解差不多？ |
|
l****i
发帖数: 2772 | 42 首先，我不是反问。所有的onsite，我都是笑脸相迎。
其次，10分钟解释phd的东西，很难讲的很全很细。简单问一下面试官对这个方面的熟
悉程度，我能明白从哪里讲起。我的目的是在10分钟内，尽可能清晰易懂的让面试官了
解我的工作。
我一直觉得自己很一般，“咄咄逼人”，我不至于傻到对面试官“咄咄逼人”。3年国
内国企的经历，让我认识到了什么叫错综复杂的人际关系。人脉在公司内，比技术水平
更重要。所以我早就没了年少的轻狂。
我目前的面试经历，确实遇到一些技术上很强的面试官，也遇到了一些感觉水平很水的
面试官。我目前唯一反驳过面试官的一次，就是onsite 3的那个老中hire manager，当
时讨论到二个算法的复杂度，O（nlogn）和O（n），我说我的解法是O（n），所以比另
外一个需要先排序的解法O（nlogn）要好。他回复我，O（nlogn）因为包含了logn，所
以比你的O（n）要好。我在实在无奈的情况下，反驳了他。如果因为这个问题，他把我
据了，我也没什么好遗憾的。
至于国人面试官的问题，我每次遇到国人面试官，内心都还是感觉到亲切的。我也始终
相信，大多数国人，都还是帮助同胞... 阅读全帖 |
|
l****i
发帖数: 2772 | 43 谢谢你的回复。
如果你觉得，面试等于考试，我个人不是很赞同。比如，为什么会有人，答的都对，却
拿不到offer？面试注重的是交流。公司里的大多数活，基本上，有点基础的人，都可
以干。
和面试官争辩，请看看我上面发的一段，请你指导一下，这时候是否需要争辩。我也不
确定，这种情况下，争辩是错还是对。如果面试官明显错了，我不争辩？那结果，还是
我是错的。
"我目前唯一反驳过面试官的一次，就是onsite 3的那个老中hire manager，当
时讨论到二个算法的复杂度，O（nlogn）和O（n），我说我的解法是O（n），所以比另
外一个需要先排序的解法O（nlogn）要好。他回复我，O（nlogn）因为包含了logn，所
以比你的O（n）要好。"
我觉得，“请问你对XXX有多少了解”。和你说的，“你对XXX懂不懂”，还是差异蛮大
的。10分钟，基本上就是一个elevator talk，对于不同背景的听众，给不同难度的
talk，这个我个人觉得，完全是可以理解的，也有利于听众对你内容价值的判断。 |
|
e*******8
发帖数: 94 | 44 哎，大牛我可不敢当啊-_-bbbb
我刚才想错了，那步preprocess也需要O(nlogn).
完整的算法大致是这样：
１.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
所以最后整个算法的时间复杂度是O(nlogn). |
|
e*******8
发帖数: 94 | 45 哎，大牛我可不敢当啊-_-bbbb
我刚才想错了，那步preprocess也需要O(nlogn).
完整的算法大致是这样：
１.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
所以最后整个算法的时间复杂度是O(nlogn). |
|
i******t
发帖数: 22541 | 46 对每个白点 在黑点钟查找最近的 用kd tree 之类的 binary tree
建树 大概 nlogn ?
查找 logn
所以 总的复杂度是 假设 白点个数也是 n
nlogn + logn n = 2nlogn = nlogn
不知道对不对 |
|
k*****e
发帖数: 93 | 47 For the second question:
Programming problem: given a vector, check if two elements inside it can add
to a given value.
How did you do it?
A brute-force method is to check all kinds of combinations of two elements.
The complexity is O(n^2).
But if you first sort, it takes O(nlogn). Then for each element a[i], search
(value - a[i]) in a sorted array. It takes O(logn). So totally O(nlogn)
again. The whole complexity is O(nlogn).
how
one
add |
|
r*g
发帖数: 186 | 48 先生成convex hull
然后考虑边界点的两两距离
convex hall生成算法是O(nlogn)
然后在convex hull上寻找两两最长点 复杂度是O(nlogn)
合计复杂度O(nlogn) |
|
w****e
发帖数: 586 | 49 不知道你在折腾什么。第一个follow up都和你说了从后往前找符合条件的最长序列，
一个for loop，O(1) space就搞定了的事
第二个follow up，其实就是在问符合条件的连续最长子序列是多长。O(nlogn)时间的
做法恐怕不少，这是一个：
1. 对每个元素，创建一个二元组，（value，index）
2. sort这些二元组based on value。
第1、2步其实就是带着index sort一把。时间O(nlogn)
3. 创建一个与原数组等长的数组bool visited[]，初始化0
4. 按着value从大到小遍历排序好的二元组
4a. 如果visited[index]>0, continue
4b. 否则，按index回到原来数组，从该元素出发向左向右走到不能走（出现负数
并且平方超过该元素）位置。路上经过的所有数全部把相应visited位置改成1。比较此
时序列长度是否超过已发现的最长子序列。如是则记录此时序列长度。
最后输出记录下来的最长子序列。
二元组只遍历一遍，原数组在visited[]的帮助下每个元素也只会被访问一次。所以第... 阅读全帖 |
|
d*****u
发帖数: 17243 | 50 简单说，先把A里的第一个数字排个序
如果用比较的方法，这个是nlogn
然后就只需要考虑比B里面小的数字，
对于B里每一个数字，查找这个区间是logn
如果B里有n个数，则是nlogn
同样，把A里的第二个数字做类似处理
然后找出比B里的大的
再跟前面的取交集
最后就是O(nlogn) |
|
