Research Space for Linear Algebra & Discrete Mathematics
他的意思是"如果我要決定砍哪兩個數字必須花2r-1次的比較"至於為什麼要花2r-1次，這不重要反正他的重點在於每一層的遞迴的cost是2r-1，所以遞迴關係式就是An = An-2 + 2r-1(如果下一題的演算法他說要花10r+65535次比較，那就是An = An-2 + 10r+65535)
無論Ar多少都是要2r-1？
fun( int r ) { if ( r == 0 || r == 1 ) return 0; for ( int i = 0 ; i < 2r-1 ;i++ ) { if ( comparison ) // (*) do something... } // for... return fun( r-2 );}然後問你請問(*)處跑了幾次r代9，A9 = 17 + A8r代8，A8 = 15 + A7...反正2r-1這傢伙也會一直縮小，你就別太在意他演算法是怎麼寫了...
好吧，感謝您的幫忙
張貼留言
6 則留言:
他的意思是
"如果我要決定砍哪兩個數字必須花2r-1次的比較"
至於為什麼要花2r-1次，這不重要
反正他的重點在於每一層的遞迴的cost是2r-1，所以遞迴關係式就是An = An-2 + 2r-1
(如果下一題的演算法他說要花10r+65535次比較，那就是An = An-2 + 10r+65535)
無論Ar多少都是要2r-1？
fun( int r ) {
if ( r == 0 || r == 1 )
return 0;
for ( int i = 0 ; i < 2r-1 ;i++ ) {
if ( comparison ) // (*)
do something...
} // for...
return fun( r-2 );
}
然後問你請問(*)處跑了幾次
r代9，A9 = 17 + A8
r代8，A8 = 15 + A7
...
反正2r-1這傢伙也會一直縮小，你就別太在意他演算法是怎麼寫了...
好吧，感謝您的幫忙
張貼留言