f*****w
发帖数: 2602 | 1 精华区里面的问题 矩阵行和列都排好了 需要按顺序打印出所有元素
1 2 3
4 5 6
7 8 9
讨论的人说用heap 但是用heap无非也要n^2lgn；
而把整个matrix认作一个数组排序其实也就n^2lgn^2 = O(n^2lgn)
还有更好的办法么？ |
f*******4
发帖数: 1401 | 2 杨氏矩阵本身就是一个heap 你一个一个输出 每次输出
后heaplify 不是应该是O(n log n)吗 怎么会是
n^2 lg n? |
C***y
发帖数: 2546 | 3 n*n的矩阵
【在 f*******4 的大作中提到】
: 杨氏矩阵本身就是一个heap 你一个一个输出 每次输出
: 后heaplify 不是应该是O(n log n)吗 怎么会是
: n^2 lg n?
|
e*****e
发帖数: 1275 | 4 young tableau就是打印(0,0)位置的值然后delete, 然后youngify |
C***y
发帖数: 2546 | 5 这个是O(n^3)的吧，有没有更好的了？
【在 e*****e 的大作中提到】
: young tableau就是打印(0,0)位置的值然后delete, 然后youngify
|
e*****e
发帖数: 1275 | 6 你这个矩阵是NXN,就是有n^2个item.
如果把它们打印出来，能好于n^2, 俺实在觉得不可能。 |
e*****e
发帖数: 1275 | 7 我也觉得我的solution 不好，那位大牛给说说，有啥好solution? |
f*****w
发帖数: 2602 | 8 youngify 是什么操作？ 难道只要O(1)就行？ |
C***y
发帖数: 2546 | 9 yougify的复杂度是O(N+M)
所以总的复杂度应该是3次方的
上面我写错了
【在 f*****w 的大作中提到】
: youngify 是什么操作？ 难道只要O(1)就行？
|
f*****w
发帖数: 2602 | |
