s******a
发帖数: 11 | 1 一家华尔街的Hedge Fund。位置是High Frequency Trading Quant
1. 如果X是一个covariance matrix, 问exp(X)是什么。-- 这题我不会，我估计是用泰
勒级数展
开，但是，X^2， X^3，...是什么，我也不太清楚。我觉着exp(X)没有实在的物理意义。
2. 设计一个算法，找到n个数当中第k大的数。问最好的算法的复杂度是多少。 |
t*****j
发帖数: 1105 | 2 1. covariance matrix的定义能详细给出么？俺只修过概率论基础课。
2. quick sorting，复杂度O(nlogn)。
义。
【在 s******a 的大作中提到】
: 一家华尔街的Hedge Fund。位置是High Frequency Trading Quant
: 1. 如果X是一个covariance matrix, 问exp(X)是什么。-- 这题我不会，我估计是用泰
: 勒级数展
: 开，但是，X^2， X^3，...是什么，我也不太清楚。我觉着exp(X)没有实在的物理意义。
: 2. 设计一个算法，找到n个数当中第k大的数。问最好的算法的复杂度是多少。
|
t*******y
发帖数: 637 | 3 1 应该就是泰勒展开吧
2 跟k没关系么 k=1 应该是O(n)
【在 t*****j 的大作中提到】
: 1. covariance matrix的定义能详细给出么？俺只修过概率论基础课。
: 2. quick sorting，复杂度O(nlogn)。
:
: 义。
|
J**********g
发帖数: 213 | 4 1. if X=UDU^T, where U is orthogonormal, ie, UU^T=I, D=diag[d_1,...,d_n] is
the eigenvalue matrix, then
exp(X)=Uexp(D)U^T=U diag[exp(d_1),...,exp(d_n)] U^T.
I don't know if this what they were looking for. |
t*****j
发帖数: 1105 | 5 没啥关系。k=1是特殊情况，因为这个是用O（1）space就能解决的。
泰勒展开的请详细说说？
【在 t*******y 的大作中提到】
: 1 应该就是泰勒展开吧
: 2 跟k没关系么 k=1 应该是O(n)
|
t*******y
发帖数: 637 | 6 exp(X)=I+X+X^2/2!+X^3/3!+...
X是matrix
不过看楼主的意思好像要写出每一项的具体形式？
【在 t*****j 的大作中提到】
: 没啥关系。k=1是特殊情况，因为这个是用O（1）space就能解决的。
: 泰勒展开的请详细说说？
|
t********a
发帖数: 810 | 7
义。
1. the hint is to think in terms of pca. exp(X) have the same eigenvectors
as X, and its eigenvalues are the exp of X's eigenvalues. Therefore exp(X)
represent the covariance matrix of data consists of the same principle
components, but the variance of the projections on each principle component
is exp of the value before.
【在 s******a 的大作中提到】
: 一家华尔街的Hedge Fund。位置是High Frequency Trading Quant
: 1. 如果X是一个covariance matrix, 问exp(X)是什么。-- 这题我不会，我估计是用泰
: 勒级数展
: 开，但是，X^2， X^3，...是什么，我也不太清楚。我觉着exp(X)没有实在的物理意义。
: 2. 设计一个算法，找到n个数当中第k大的数。问最好的算法的复杂度是多少。
|
b***k
发帖数: 2673 | 8 seach a paper
"Nineteen dubious ways to compute the exponential of a matrix,
twenty-five years later", SIAM review.
by C. Moler and C. Van Loan
义。
【在 s******a 的大作中提到】
: 一家华尔街的Hedge Fund。位置是High Frequency Trading Quant
: 1. 如果X是一个covariance matrix, 问exp(X)是什么。-- 这题我不会，我估计是用泰
: 勒级数展
: 开，但是，X^2， X^3，...是什么，我也不太清楚。我觉着exp(X)没有实在的物理意义。
: 2. 设计一个算法，找到n个数当中第k大的数。问最好的算法的复杂度是多少。
|
z****i
发帖数: 406 | 9 2。 算法应该是O(n)吧。因为只要把第k大的数找到就好了，并不需要整个排序啊。
【在 t*****j 的大作中提到】
: 1. covariance matrix的定义能详细给出么？俺只修过概率论基础课。
: 2. quick sorting，复杂度O(nlogn)。
:
: 义。
|
M*****d
发帖数: 100 | 10 2. O(n), no matter what k is.
义。
【在 s******a 的大作中提到】
: 一家华尔街的Hedge Fund。位置是High Frequency Trading Quant
: 1. 如果X是一个covariance matrix, 问exp(X)是什么。-- 这题我不会，我估计是用泰
: 勒级数展
: 开，但是，X^2， X^3，...是什么，我也不太清楚。我觉着exp(X)没有实在的物理意义。
: 2. 设计一个算法，找到n个数当中第k大的数。问最好的算法的复杂度是多少。
|
|
|
t*****j
发帖数: 1105 | 11 哦，是不需要排序的，不过好像quicksort最快。worst case应该是O(nlogn)吧？O(1)
space.O（n）算法是怎么弄的？hash table? 求教下。
【在 z****i 的大作中提到】
: 2。 算法应该是O(n)吧。因为只要把第k大的数找到就好了，并不需要整个排序啊。
|
a****9
发帖数: 418 | 12 BFPRT算法
for any k, worst case O(n)
【在 t*****j 的大作中提到】
: 哦，是不需要排序的，不过好像quicksort最快。worst case应该是O(nlogn)吧？O(1)
: space.O（n）算法是怎么弄的？hash table? 求教下。
|
S*********g
发帖数: 5298 | 13 http://en.wikipedia.org/wiki/Selection_algorithm
【在 t*****j 的大作中提到】
: 哦，是不需要排序的，不过好像quicksort最快。worst case应该是O(nlogn)吧？O(1)
: space.O（n）算法是怎么弄的？hash table? 求教下。
|
t*****j
发帖数: 1105 | |
z****i
发帖数: 406 | 15 看起来皮皮和芝麻认识？：）
【在 t*****j 的大作中提到】
: 芝麻爹也跑过来啦。谢谢了！
|
t*****j
发帖数: 1105 | 16 俺和芝麻娘一个私人club的。
【在 z****i 的大作中提到】
: 看起来皮皮和芝麻认识？：）
|
S*********g
发帖数: 5298 | 17 哈哈，我没事就来这个版打打酱油
【在 t*****j 的大作中提到】
: 芝麻爹也跑过来啦。谢谢了！
|
z****g
发帖数: 1978 | 18 1. covariance matrix is always real symmetric, which is easy to calculate
by Taylor expansion. Actually, in math, exp(x) is DEFINED by Taylor
expansion.
2. Find the max is O(logN), so, depends on K, the worst is O(N).
义。
【在 s******a 的大作中提到】
: 一家华尔街的Hedge Fund。位置是High Frequency Trading Quant
: 1. 如果X是一个covariance matrix, 问exp(X)是什么。-- 这题我不会，我估计是用泰
: 勒级数展
: 开，但是，X^2， X^3，...是什么，我也不太清楚。我觉着exp(X)没有实在的物理意义。
: 2. 设计一个算法，找到n个数当中第k大的数。问最好的算法的复杂度是多少。
|
h******g
发帖数: 69 | 19 Find the max is O(logN)? Are you sure? |
d**********9
发帖数: 5215 | 20 should be just O(n)
【在 h******g 的大作中提到】
: Find the max is O(logN)? Are you sure?
|
|
|
z****g
发帖数: 1978 | 21 o, you are right. should be O(n). I just get used to save everything
potentially need to be queried for range into a black-red tree.
【在 d**********9 的大作中提到】
: should be just O(n)
|
m**********4
发帖数: 774 | 22 Agree.
The fastest algorithm in finding the max is heap, which is O(n)
【在 h******g 的大作中提到】
: Find the max is O(logN)? Are you sure?
|
S***w
发帖数: 1014 | 23 那本板上推崇的经典算法书第9章有详细讨论
下学期一定要认真学习算法和数据结构
看大家面试，看来很有必要学习
【在 z****i 的大作中提到】
: 2。 算法应该是O(n)吧。因为只要把第k大的数找到就好了，并不需要整个排序啊。
|
d**********9
发帖数: 5215 | 24 哪一本书？谢谢
【在 S***w 的大作中提到】
: 那本板上推崇的经典算法书第9章有详细讨论
: 下学期一定要认真学习算法和数据结构
: 看大家面试，看来很有必要学习
|
s*******0
发帖数: 3461 | 25 同问 哪一本书？
【在 d**********9 的大作中提到】
: 哪一本书？谢谢
|
S***w
发帖数: 1014 | 26 Introduction to algorithm by Thomas H.Cormen |
