(b)for (a=l; a<=n; a*=2)
for (b=l; b<=a; b++)
C++;
(c)for (a=l; a<=n; a*=2)
for (b=l; b<=a; b*=2)
C++;
--
(b)我解出來是 2n-1
(c)我解出來是 [(lgn+2)lgn]/2
請問這樣對嗎...
Research Space for Linear Algebra & Discrete Mathematics
13 則留言:
yes 你速隨 ?
問題板上有人解了 XD
麻煩助教解一下這題(T/F)，我覺得是false..但有人證true有人證false~
If A is diagonalizable, then the rank of A equals the number
: of nonzero eigenvalues of A.
TRUE 可對角化具N個LI EIGENVECTOR
rank(AP)=RANK(PD) P可逆!
SiG:第一題跟你一樣, 第二題我算(lgn+2)(lgn+1)/2
Mango:答案是False
對齁 還少算一項的樣子
在短短的幾個推文又有兩種答案= =
請問這題的答案是?
(b)不失一般性假設n = 2^k
當a = 1時, 內部迴圈執行1次
當a = 2時, 內部迴圈執行2次
當a = 4時, 內部迴圈執行4次
...
當a = 2^k時, 內部迴圈執行2^k次
所以複雜度2^0 + 2^1 + ... + 2^k
= 2^(k+1)-1 = 2n - 1 = O(n)
(c)類似上面的討論
複雜度1+2+...+k = k(k+1)/2
=(1/2)(logn(logn+1)) = O((logn)^2)
A可對角化, 則存在可逆矩陣P使得
P^(-1)AP = D
=> A = PDP^(-1)
=> rank(A) = rank(D)
因為D為對角矩陣, 所以rank(D)為D的對角項的非零項個數, 即非零eigenvalue個數,不過這裡要含重數一起算, 也就是eigenvalue為2, 2, 3, 0, 0要算成3個非零eigenvalue
這題答案是True
張貼留言