有谁知道BIOSTAR TH61-ITX主板自带的遥控是啥芯片的？ - 未名空间MITBBS历史存档

有谁知道BIOSTAR TH61-ITX主板自带的遥控是啥芯片的？# Hardware - 计算机硬件

h*k2011-12-29 08:12

1 楼

求the first k largest elements in a unsorted array.
如果k很小，比如3，n很大，比如100000，用什么算法最好？
如果k很大，接近n，用什么算法好？
进一步问如何求前 k1至 k2个最大元素（k1如果有duplicate value在数组中，你的算法还可以么？
将来如果有机会面试别人，我一定出这道题。可惜要先找到工作，:-(

z*02011-12-29 08:12

2 楼

我的linux认出来是ITE啥的，但看其自带的windows驱动里的INF文件，却是nuveton啥
的。懒得为了确认驱动，再专门去装个windows
有谁知道的吗？谢谢

m*o2011-12-29 08:12

3 楼

真有闲心

【在 h**k 的大作中提到】

: 求the first k largest elements in a unsorted array.
: 如果k很小，比如3，n很大，比如100000，用什么算法最好？
: 如果k很大，接近n，用什么算法好？
: 进一步问如何求前 k1至 k2个最大元素（k1: 如果有duplicate value在数组中，你的算法还可以么？
: 将来如果有机会面试别人，我一定出这道题。可惜要先找到工作，:-(

r*o2011-12-29 08:12

4 楼

试着答一下。

就顺序比较吧，每个比较k次，复杂度O(kn)
可以排序，或binary search，或用min heap，复杂度分别是O(nlgn),O(nlgn),O(klgn)
先找出第k1大的元素，再找出第k2大的元素，介于这两者之间的元素就是所求的元素。
复杂度O(k2 lgn)
binary search的方法可能不行了，用排序和min heap应该还可以。

【在 h**k 的大作中提到】

: 求the first k largest elements in a unsorted array.
: 如果k很小，比如3，n很大，比如100000，用什么算法最好？
: 如果k很大，接近n，用什么算法好？
: 进一步问如何求前 k1至 k2个最大元素（k1: 如果有duplicate value在数组中，你的算法还可以么？
: 将来如果有机会面试别人，我一定出这道题。可惜要先找到工作，:-(

h*k2011-12-29 08:12

5 楼

klgn)
用min heap的复杂度是O(nlogk),heap的大小是k，一共插入n个元素。
用binary search的思路可以实现O(n+k)
可以的，需要改一下算法。

【在 r****o 的大作中提到】

: 试着答一下。
:
: 就顺序比较吧，每个比较k次，复杂度O(kn)
: 可以排序，或binary search，或用min heap，复杂度分别是O(nlgn),O(nlgn),O(klgn)
: 先找出第k1大的元素，再找出第k2大的元素，介于这两者之间的元素就是所求的元素。
: 复杂度O(k2 lgn)
: binary search的方法可能不行了，用排序和min heap应该还可以。

r*o2011-12-29 08:12

6 楼

恩，我写错了。
能不能说说用binary search怎么实现O(n+k)啊? 我觉得有binary search，复杂度里面
应该有个lg啊。
能否说说怎么改进?

【在 h**k 的大作中提到】

:
: klgn)
: 用min heap的复杂度是O(nlogk),heap的大小是k，一共插入n个元素。
: 用binary search的思路可以实现O(n+k)
: 可以的，需要改一下算法。

a*d2011-12-29 08:12

7 楼

"如果k很大，接近n，用什么算法好".
similar to the case that k is small.
Because, we can eliminate (n-k) smallest elements, and remaining ones are k
largest.

klgn)

【在 r****o 的大作中提到】

: 试着答一下。
:
: 就顺序比较吧，每个比较k次，复杂度O(kn)
: 可以排序，或binary search，或用min heap，复杂度分别是O(nlgn),O(nlgn),O(klgn)
: 先找出第k1大的元素，再找出第k2大的元素，介于这两者之间的元素就是所求的元素。
: 复杂度O(k2 lgn)
: binary search的方法可能不行了，用排序和min heap应该还可以。

h*k2011-12-29 08:12

8 楼

其实是类似quick sort的思路，每次二分数组的时候，得到前半个部分的大小，如果小
于k,则舍弃后半部分，否则输出前半部分，在后半部分找剩下的。

【在 r****o 的大作中提到】

:
: 恩，我写错了。
: 能不能说说用binary search怎么实现O(n+k)啊? 我觉得有binary search，复杂度里面
: 应该有个lg啊。
: 能否说说怎么改进?

h*e2011-12-29 08:12

9 楼

那也不是O(n+k)

【在 h**k 的大作中提到】

:
: 其实是类似quick sort的思路，每次二分数组的时候，得到前半个部分的大小，如果小
: 于k,则舍弃后半部分，否则输出前半部分，在后半部分找剩下的。

r*o2011-12-29 08:12

10 楼

这个复杂度好像是O(n lgk)

【在 h**k 的大作中提到】

:
: 其实是类似quick sort的思路，每次二分数组的时候，得到前半个部分的大小，如果小
: 于k,则舍弃后半部分，否则输出前半部分，在后半部分找剩下的。

h*k2011-12-29 08:12

11 楼

第一次需要比较整个数组，c*n次运算，c是常数，第二次只需要比较一半的数组，c*n/
2，。。。，
总的运算次数是c*n+c*n/2+c*n/4+... <= c*2*n
因为一定要输出k个值，所以最终是O(n+k)

【在 h*******e 的大作中提到】

: 那也不是O(n+k)

l*a2011-12-29 08:12

12 楼

for unsorted array,how do you know which should be discarded
and which should be kept

【在 h**k 的大作中提到】

: 第一次需要比较整个数组，c*n次运算，c是常数，第二次只需要比较一半的数组，c*n/
: 2，。。。，
: 总的运算次数是c*n+c*n/2+c*n/4+... <= c*2*n
: 因为一定要输出k个值，所以最终是O(n+k)

h*e2011-12-29 08:12

13 楼

depends on how u choose the pivot, this is expected O(N) on average, not
worst case.

n/

【在 h**k 的大作中提到】

: 第一次需要比较整个数组，c*n次运算，c是常数，第二次只需要比较一半的数组，c*n/
: 2，。。。，
: 总的运算次数是c*n+c*n/2+c*n/4+... <= c*2*n
: 因为一定要输出k个值，所以最终是O(n+k)

h*k2011-12-29 08:12

14 楼

randomly choose the pivot.

【在 h*******e 的大作中提到】

: depends on how u choose the pivot, this is expected O(N) on average, not
: worst case.
:
: n/

g*e2011-12-29 08:12

15 楼

这个思路是divide and conquer，不是binary search。经典的求k largest element的
算法之一，不需要是sorted array。但平均time complexity是nlogn.

【在 h**k 的大作中提到】

: randomly choose the pivot.

y*52011-12-29 08:12

16 楼

CLRS Selection in expected (also has worst-case) linear time. O(n)
不过我觉得在面试中只要答出expected linear time的算法就可以了吧。

m*v2011-12-29 08:12

17 楼

真正O(n)的算法很复杂

【在 y******5 的大作中提到】

: CLRS Selection in expected (also has worst-case) linear time. O(n)
: 不过我觉得在面试中只要答出expected linear time的算法就可以了吧。

p*y2011-12-29 08:12

18 楼

怎么看上去很象以前Google问我的题。。。

【在 h**k 的大作中提到】

: 求the first k largest elements in a unsorted array.
: 如果k很小，比如3，n很大，比如100000，用什么算法最好？
: 如果k很大，接近n，用什么算法好？
: 进一步问如何求前 k1至 k2个最大元素（k1: 如果有duplicate value在数组中，你的算法还可以么？
: 将来如果有机会面试别人，我一定出这道题。可惜要先找到工作，:-(