s******n
发帖数: 3946 | 1 那上面写，假设n=k, n趋向无穷大的话，n面全显示的平均次数是nlog(n)。 |
|
v***n
发帖数: 562 | 2 看了WIKI
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
但是binary search那段还是不明白，有哪位大侠明白的讲一下，多谢！
L = 0
for i = 1, 2, ... n:
binary search for the largest positive j ≤ L
such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
P[i] = M[j]
if j == L or X[i] < X[M[j+1]]:
M[j+1] = i
L = max(L, j+1) |
|
|
|
i**********e
发帖数: 1145 | 5 这题我记得有论文说 O(n) 可以解，但是算法非常复杂。
用堆 O(k log n) 就应该可以了。
请问 O(n log n) 有比 O(k log n) 快一些吗？ |
|
f*******n
发帖数: 12623 | 6 你弄错了什么东西。如果T(N) = O(\sqrt(N)) + T(3N/4) ，那T(N) = O(\sqrt(N))。
证明：O(\sqrt(N)) + T(3N/4) = O(\sqrt(N)) + O(\sqrt(3N/4)) = O(\sqrt(N)) ＋
\sqrt(3/4)O(\sqrt(N)) = O(\sqrt(N)) = T(N) |
|
h********e
发帖数: 1972 | 7 k 可以是n^2... nlogn 这里的n就是矩阵的边长。 klogn有可能比直接做还慢。。 |
|
|
i****s
发帖数: 1152 | 9 基本上都是median of median的变种
理论上是O(N)
4 |
|
f*******n
发帖数: 12623 | 10 sqrt(N)+sqrt(3N/4)+sqrt(9N/16)+sqrt(3^3 N/4^3) = sqrt(N) * (1+sqrt(3/4)+sqrt
(3/4)^2+sqrt(3/4)^3+...)
1+sqrt(3/4)+sqrt(3/4)^2+sqrt(3/4)^3+...是geometric series。一直加起来＝1/(1-
sqrt(3/4))，是一个constant。所以是sqrt(N) * O(1) = O(sqrt(N))
log |
|
h********e
发帖数: 1972 | 11 唔那我递归方程写错了，本意是。。应该是T(N) = O(n) + T(3N/4) 不好意思。。 |
|
|
s*********5
发帖数: 514 | 13 一百万个amazon product id，问过去一小时销售量top 10的(map-
reduce)
这个还要用到map-reduce, 答错方向了吧。
这是从N个数中找最大的k个数，修改一下quicksort, 或者用heapsort, with a heap
of size of k.
heap build time: Nlog(k)
sort time: klog(k)
here N=1,000,000, k = 10,
total operation less than 4 million, 2G clock, 也就几个微秒的事情。
数据量不上T，单次map计算时间少于1分钟，都没必要map-reduce |
|
s*********5
发帖数: 514 | 14 注意是O(Nlog(K)), here log(K) = 4.
比InsertSort还是要快一点。
用QuickSort的修改版，就是只排最大的10个。推而广之就是找第K个大的数，一个应用
是找median, 每次都扔掉一半数据，因此平均复杂度是O(2N)。
为了提高worst case performance, 用median of medians算法。 自己搜吧。 |
|
d****n
发帖数: 1637 | 15 my solution
runningtime
space O(1)
any suggestions or improvement?
///file mitbbs.c
#include
int arr[]={-5,2,-3,4,-8,-9,1,3,-10};
int sz=9;
void print_arr();
int main(){
print_arr();
int i,j,k,t;
for(i=0,k=0;i
if(arr[i]<0 ){
t=arr[i];
for(j=i-1;j>=k ;j-- ){
arr[j+1]=arr[j];
... 阅读全帖 |
|
s*********5
发帖数: 514 | 16 Suppose you have two group divided, to reduce the current distance between
the group, S1, S2, you need be able to swap two elements in the two group.
Therefore, we should reserve the pair of numbers with the smallest distance.
So an algorithm should be to sort the numbers first, then divide them into
pairs, starting from the smallest distance available. Then divide each pair
into the two groups.
nlog + n |
|
h********e
发帖数: 1972 | 17 请不要吧2写到 O notation里面。。这样显得很不专业。。kO(n)基本等于O(n^2)还可能更慢。。k may even be (n^2)/2。。
这样就太慢了。。O(n)的算法很难不会考到的。会做O(nlog n)就可以了。跟k没关系。 |
|
s******t
发帖数: 169 | 18 离散化+线段树可以做，或者离散化+树状数组，对于每个pair，直接插入，时间为log(
n)，总共为nlog(n)。然后查询的时候，每次查询log(n)
wwwyhx说的本质上就是离散化吧，如果我没理解错的话。本质上相当于把一个相当大的
区间离散成较小的区间，比如说有一个对是(1,100000)另一个是(2,300000)，真用一个
300000的数组去存就不太划算了，其实把几个点排下序然后离散化，4个点就可以 |
|
H*******g
发帖数: 6997 | 19 我感觉版上有无数学院派的，说白了就是整天盯着算法看的，背题目的。
版上还有几个牛人显然是实用派的，也就是已经在IT领域内工作并有小成/大成的
俺也算是个实用派，每次看到版上发的那些算法题俺就特惭愧，因为完全不懂哇。。。
我既没找过什么KTH，也没用过NLOG，但这似乎并不能阻碍我成为框架师。所以我也不
懂了，一方面吧，我觉得懂算法的都很牛，另一方面有觉得搞算法的似乎理论性都太强
了点。
我很困惑为什么版上就没几个愿意进入我们应用领域的呢？俺承认，这个帖子灰常的无
厘头。 |
|
v****c
发帖数: 29 | 20 不知道有没有O(n)的算法
O(nlog n)的算法还是很好想的吧
每次花n的时间吧block大小变成一半 |
|
l**********g
发帖数: 426 | 21 数组 3, 5,1, 8, 9, 7, 0, 2
找到 3, 1, 0, 2 ----最长序列
要求复杂度好于 O(nlog(n))
有hashmap记录间隔的解法，写起来蛮复杂。
大侠指点。 |
|
s*******f
发帖数: 1114 | 22 jingo 你狠彪悍！！
//码遍本版
//: 数组 3, 5,1, 8, 9, 7, 0, 2
//: 找到 3, 1, 0, 2 ----最长序列
//: 要求复杂度好于 O(nlog(n))
//i use static linked list here
//change map to hash_map, then O(n)
struct NodeInfo{
int data;
int next;
bool has_pre;
NodeInfo(int d):data(d), next(-1), has_pre(false){ }
NodeInfo(){}
};
vector MaxForSeq(int a[], int len){
vector ret;
vector vn(len);
map mp; //data to index in vector vn
for (int i = 0; i < len; ++i){
if (mp.... 阅读全帖 |
|
|
C***U
发帖数: 2406 | 24 1 Make a sorted copy of the sequence A, denoted as B. O(nlog(n)) time.
2 Use Longest Common Subsequence on with A and B. DP(O(n^2)时间）
是O(n^2)时间了 比最优的要差一些了
刚才搞错了 |
|
d*s
发帖数: 699 | 25 是这样的矩阵么？
1 3 5
2 7 8
6 9 11
如果是的话，可以按照/分层，每层都比上一层大，比如第一层是1，第二层是2,3,第三
层6 7 5等等
对于NxN矩阵中第k个最小的数字，所处的层数n由max n for k-n*(n+1)/2>0得到，然后
对该层(n+1)所有数字排序，复杂度nlog(n)，取第int(k-n*(n+1)/2)个，得到结果 |
|
|
|
q****m
发帖数: 177 | 28 O(n^2)还ok,就是基本的DP. O(nlog n )怎么实现还没想通 |
|
d**e
发帖数: 6098 | 29 ☆─────────────────────────────────────☆
HorseKing (二逼青年思路广) 于 (Mon Apr 23 21:49:20 2012, 美东) 提到:
我感觉版上有无数学院派的，说白了就是整天盯着算法看的，背题目的。
版上还有几个牛人显然是实用派的，也就是已经在IT领域内工作并有小成/大成的
俺也算是个实用派，每次看到版上发的那些算法题俺就特惭愧，因为完全不懂哇。。。
我既没找过什么KTH，也没用过NLOG，但这似乎并不能阻碍我成为框架师。所以我也不
懂了，一方面吧，我觉得懂算法的都很牛，另一方面有觉得搞算法的似乎理论性都太强
了点。
我很困惑为什么版上就没几个愿意进入我们应用领域的呢？俺承认，这个帖子灰常的无
厘头。
☆─────────────────────────────────────☆
StevenLow (CrossLayer) 于 (Mon Apr 23 21:49:55 2012, 美东) 提到:
马哥牛逼。
☆─────────────────────────────────────☆
yangc... 阅读全帖 |
|
c********t
发帖数: 5706 | 30 好像是O(m*n)? 用heap是 O(nlog(m))吧 |
|
|
c********r
发帖数: 286 | 32 希望对Recursion Big-O complexity 分析有些疑惑的童鞋有些帮助
Recurrence Algorithm Big-O Solution
T(n) = T(n/2) + O(1) Binary Search O(log n)
T(n) = T(n-1) + O(1) Sequential Search O(n)
T(n) = 2 T(n/2) + O(1) tree traversal O(n)
T(n) = T(n-1) + O(n) Selection Sort (other n2 sorts) O(n^2)
T(n) = 2 T(n/2) + O(n) Mergesort (average case Quicksort) O(nlog n) |
|
e****e
发帖数: 418 | 33 来自主题: JobHunting版 - 请教一道题 I think sort+scan is a good approach. If there is a range for the value of
elements, then bitmap is good too.
Time complexity.
The first one is nlog(n).
Second one is n+k. k is the size of the range.
Depending on the the characteristics/property/pattern of data in the array,
choose one of the two approaches. |
|
d*****y
发帖数: 1365 | 34 我的帖子里面写了，不需要把矩阵完全构建出来。我用矩阵只是为了描述的方便。
实际上每次找到一个数，就把他左边和下边的数算出来，这样的话，挑N个数，每个数
要算他的左邻和下方的邻居。一共只需要算2*N个值，heap操作是 N log N, 排序nlogn
, 所以总共的复杂度nlog n
. |
|
j**7
发帖数: 143 | 35 另外一个方法是用sort,然后再找重复的element.这样就不会有integer overflow,但是
time complexity 是 nlog(n).
Arrays.sort(list);
for(int i=0;i
{
if(list[i]==list[i+1])
return list[i];
} |
|
a*******3
发帖数: 27 | 36 对N个数组中的最大元素开始做二分，找到一个最小的m，是的N个数组中恰好有>=k个数
小于等于m，那么m就是所求。
每次求N个数组中多少个元素小于等于m，nlogn，最多二分32或者64次（取决于数据是
32位还是64位），这样看的话是nlogn的，只不过常数有点大
如果不认为这个实常数，那么就是nlog(n)log(max_value-min_value)
klogn的问题是，k可能很大，如果k~n^2/2，那复杂度就高上去了 |
|
s********x
发帖数: 914 | 37 这个有意思
v1理论上是 （nlog(n) + n）* T1 这个constant T1 不需要hash的operation，肯定要
小些
v1完全可以优化更多。
首先把array inplace quick sort， 这样就是ordered
然后search的时候完全不用linear time
贴一下哈（不知道v2和v3可否用这种思路）
// find longest increasing continuous sequence, better than O(n). a is
sorted already
public static int findLongestIncreasingContinuousSequence(int[] a) {
if (a == null || a.length == 0)
return 0;
int max = 1;
int end = 0;
// len = j - i + 1
int i = 0, k = 0;
... 阅读全帖 |
|
s********x
发帖数: 914 | 38 v1的bottle neck是quick sort inplace， worst case 也是nlog(n)
跟average case是一样的 |
|
p*****2
发帖数: 21240 | 39
worst case 也是nlog(n)
are you really sure? |
|
s********x
发帖数: 914 | 40 我找到proof啦 - quick sort worst case is nlog(n)
Data Structures
& Algorithms
in Java
Second Edition
Robert Lafore
page 725
TABLE 15.3 Comparison of Sorting Algorithms
Sort Average Worst Comparison Extra Memory
Bubble O(N2) O(N2) Poor No
Selection O(N2) O(N2) Fair No
Insertion O(N2) O(N2) Good No
Shellsort O(N3/2) O(N3/2) — No
Quicksort O(N*logN) O(N2) Good No
Mergesort O(N*logN) O(N*logN) Fair Yes
Heapsort O(N*logN) O(N*logN) Fair No |
|
s********x
发帖数: 914 | 41 quick sort worst case is nlog(n) |
|
s********x
发帖数: 914 | 42 比如quick sort吧。
如果用Parallel threads把array分成几个section来sort，应该比nlog(n)更快吧。这
样不是很多interview问题就不是最优解了吗？ |
|
s********x
发帖数: 914 | 43 是啊，但是paralellized不就可以超过nlog(n)吗。一般的merge sort是sequential的。 |
|
e*******i
发帖数: 56 | 44 BrianKWong, Would you please post O( nlog(n) ) solution to the second
problem? Thanks.
Any DaNu? Show your muscle. |
|
s*******r
发帖数: 2697 | 45 第一题不要这么复杂吧
不考虑溢出
1.先排序 nlog(n)
2.
int sum = a[0];
for (i=1;i
if((b-sum)%(n-i-1)==0){
int tmp = (b-sum)/(n-i-1);
if(tmp>=a[i-1]&&tmp
return tmp;
}
sum+=a[i];
}
return NOT_FIND;
=
)) |
|
v********n
发帖数: 18 | 46 mark nn【在 houqingniao (候情鸟)的大作中提到：】n：嗯，一样的想法。n：应该就
这样吧。n：【 在 sunfaquir (非礼勿言) 的大作中提到: 】n：: 第一题不要这么复
杂吧n：: 不考虑溢出n：: 1.先排序 nlog(n)n：: 2.n……nn--n[发自未名空间
Android客户端] |
|
s*******r
发帖数: 2697 | 47 第一题不要这么复杂吧
不考虑溢出
1.先排序 nlog(n)
2.
int sum = a[0];
for (i=1;i
if((b-sum)%(n-i-1)==0){
int tmp = (b-sum)/(n-i-1);
if(tmp>=a[i-1]&&tmp
return tmp;
}
sum+=a[i];
}
return NOT_FIND;
=
)) |
|
v********n
发帖数: 18 | 48 mark nn【在 houqingniao (候情鸟)的大作中提到：】n：嗯，一样的想法。n：应该就
这样吧。n：【 在 sunfaquir (非礼勿言) 的大作中提到: 】n：: 第一题不要这么复
杂吧n：: 不考虑溢出n：: 1.先排序 nlog(n)n：: 2.n……nn--n[发自未名空间
Android客户端] |
|
x***y
发帖数: 633 | 49 Find max and min of A, if lenght(A) = max-min+1, the whole array is O(n);
otherwise, consider the subarray that only contains max or min O(n); finally
,consider the 3 subarrays that contains neither max nor min.
so T(n) = 3T(n/3)+O(n) => T(n) = nlog(n) |
|
|
