打印全部1-n的值，空间复杂度为O(n),时间复杂度应该是O(n^2)，系数很小。$n=10^5$，时间是10秒钟。
Block[{level=100,y},y=TableBinomial,{k,0,Floor}],{nn,level-1,level}];
Association[-1->1/2(2^level-1-y[[-2]]),0->1/2(y[[-1]]+2y[[-2]]+1),1->1/2(2^level-y[[-1]]-y[[-2]])]]
再进一步优化，用递推公式，空间复杂度为O(n),时间复杂度O(n)。
Block[{level=100,y},y=RecurrenceTable[{(8+4 n) y+(-10-4 n) y+(3+n) y+(-7-2 n) y+(n+4) y==0,y==1,y==1,y==1,y==3},y,{n,level}][[-2;;-1]];
Association[-1->1/2(2^level-1-y[[-2]]),0->1/2(y[[-1]]+2y[[-2]]+1),1->1/2(2^level-y[[-1]]-y[[-2]])]]
空间复杂度为O(1),时间复杂度O(n),计算$n=10^5$，时间是1秒钟。$n=5*10^5$，时间是17秒钟。$n=10^6$需要61秒钟。
Block[{level=100,y},y=Nest[{#[]+1,{#[],#[],#[],-{8+4 #[] ,-10-4 #[],3+#[] ,-7-2 #[] }.#[]/(#[]+4)}}&,{0,{1,1,1,3}},level-1][];
Association[-1->1/2(2^level-1-y[[-2]]),0->1/2(y[[-1]]+2y[[-2]]+1),1->1/2(2^level-y[[-1]]-y[[-2]])]]
ans=Block[{level=100,y},y=RecurrenceTable[{(8+4 n) y+(-10-4 n) y+(3+n) y+(-7-2 n) y+(n+4) y==0,y==1,y==1,y==1,y==3},y,{n,level}];
Table[{1/2(2^i-1-y[]),1/2(y[]+2y[]+1),1/2(2^i-y[]-y[])}/2^i,{i,level}]];data=N];ListLinePlot rust原生支持128位整数，计算$n=100$刚好可以不用大数运算库GMP.
use std::collections::VecDeque;
use std::time::SystemTime;
fn main() {
let epoch = SystemTime::now();
println!("{:?}",SystemTime::now().duration_since(SystemTime::UNIX_EPOCH));
let mut pool = VecDeque::from();
let n: u128 = 127;
let mut all: u128 = 1;
for i in 0..n{
all *=2;
if i>=n-30{
let bob = (all-1-pool)/2;
let equal = pool+(1+pool)/2;
let alice = (all-pool-pool)/2;
print!("{:<5}(hh<ht): {:<w$}\t(hh=ht): {:<w$}\t\t(hh>ht): {:<w$}",i+1,bob,equal,alice,w=36);
// println!();
let a = all as f64;
println!("\t\t({:>.p$},{:>.p$},{:>.p$})",(bob as f64)/a, (equal as f64)/a, (alice as f64)/a,p=6);
}
// let tmp = ((7+2*i)*pool-(3+i)*pool+(10+4*i)*pool-(8 + 4*i)*pool)/(i+4);
let tmp =(pool-pool)-(pool-pool+6*(pool-pool)-2*pool)/(i+4)+pool+4*(pool-pool);
pool.push_back(tmp);
pool.pop_front();
}
println!("cost {:?}",SystemTime::now().duration_since(epoch));
}
Ok(1715305152.343156169s)
99 (hh<ht): 307887475013879139393113690181 (hh=ht): 36009411781510700350786269593 (hh>ht): 289928413318724861004451642914 (0.485761,0.056813,0.457426)
100(hh<ht): 615866238418960422359689555420 (hh=ht): 71656412569848144755925222552 (hh>ht): 580127949239420834381088427404 (0.485833,0.056527,0.457640)
101(hh<ht): 1231912311048689813518102077359 (hh=ht): 142598837466334784225524791615 (hh>ht): 1160790051941434205249779541778 (0.485904,0.056245,0.457851)
102(hh<ht): 2464178941349203194725083875170 (hh=ht): 283790833663728134305743692045 (hh>ht): 2322632625899986276955985254289 (0.485974,0.055968,0.458059)
103(hh<ht): 4929056085463700688217714200622 (hh=ht): 564809220414940052524497334288 (hh>ht): 4647339495947194471231414108098 (0.486042,0.055694,0.458263)
104(hh<ht): 9859488212309328994987325550483 (hh=ht): 1124154023142340240517695767352 (hh>ht): 9298767368200001188442229968181 (0.486110,0.055425,0.458465)
105(hh<ht): 19721688759542342617402155703713 (hh=ht): 2237536306817887597387407464263 (hh>ht): 18605594140943110633104939404056 (0.486177,0.055160,0.458663)
106(hh<ht): 39448724588704108863597286272374 (hh=ht): 4453835870066236514894489349075 (hh>ht): 37227077955836336317297229522615 (0.486243,0.054898,0.458859)
107(hh<ht): 78907991781738909149488948394304 (hh=ht): 8865797301684336543573865432290 (hh>ht): 74485487745790117698515196461534 (0.486308,0.054640,0.459052)
108(hh<ht): 157836772793264571940604258355357 (hh=ht): 17649015920351808224546987292201 (hh>ht): 149032764944810346618004774928698 (0.486372,0.054385,0.459243)
109(hh<ht): 315714545809972501460556537149596 (hh=ht): 35135160858420086644545191816522 (hh>ht): 298187400648460865461210312186394 (0.486435,0.054134,0.459430)
110(hh<ht): 631509962155341817566965816189309 (hh=ht): 69949047969318139938823935347876 (hh>ht): 596615204509046949626834330767839 (0.486498,0.053887,0.459616)
111(hh<ht): 1263179456987412039192492596883553 (hh=ht): 139264282409834451857875506251785 (hh>ht): 1193704689870167323214880061474710 (0.486559,0.053643,0.459798)
112(hh<ht): 2526673662150169098287635629201204 (hh=ht): 277278013488731622057191671178350 (hh>ht): 2388345182895926908185669028840542 (0.486620,0.053402,0.459979)
113(hh<ht): 5053968379280585438428529728859433 (hh=ht): 552088315797063400567108419567985 (hh>ht): 4778537021992006418065354510012774 (0.486679,0.053164,0.460156)
114(hh<ht): 10109162359781076236697817439593532 (hh=ht): 1099306519191176387162010826312597 (hh>ht): 9560718555167057890262157050974255 (0.486738,0.052930,0.460332)
115(hh<ht): 20220743629525292167686324928261106 (hh=ht): 2189000577664067438060679252058024 (hh>ht): 19128630661089261422496966453441638 (0.486797,0.052698,0.460505)
116(hh<ht): 40446261899842590283054612158941299 (hh=ht): 4359026223737111015710426807047457 (hh>ht): 38271461612977540757722902301532780 (0.486854,0.052470,0.460676)
117(hh<ht): 80901949449692192531156231410113016 (hh=ht): 8680591820566911868155191617122762 (hh>ht): 76570958202855379713664459507807294 (0.486911,0.052244,0.460845)
118(hh<ht): 161822508226277671295484110632737349 (hh=ht): 17287220013959439466838213064540052 (hh>ht): 153197270705991857463629441372808743 (0.486967,0.052022,0.461011)
119(hh<ht): 323681761425943154394097095810157537 (hh=ht): 34428387568130491981716156981180721 (hh>ht): 306503848898384290076090277348834030 (0.487022,0.051802,0.461176)
120(hh<ht): 647436085364899072133896711678848780 (hh=ht): 68568341261558583848909110250321227 (hh>ht): 613223569158458216921001238351174569 (0.487077,0.051585,0.461338)
121(hh<ht): 1295015479578475017690911586952670364 (hh=ht): 136567004343852607108827635393852672 (hh>ht): 1226873507647504121007874898214166116 (0.487131,0.051371,0.461499)
122(hh<ht): 2590314019638860849124577431822184903 (hh=ht): 272008735229095616113668527840944172 (hh>ht): 2454589228271707026376982281458249229 (0.487184,0.051159,0.461657)
123(hh<ht): 5181187191772509668867633090757442629 (hh=ht): 541794513810454007132444249630601521 (hh>ht): 4910842260696363307230379141854712458 (0.487237,0.050950,0.461813)
124(hh<ht): 10363479035203180621593202533340026436 (hh=ht): 1079197176467460732607108771855237206 (hh>ht): 9824971720888012612260601659290249574 (0.487288,0.050744,0.461968)
125(hh<ht): 20729140618243485957128312090435736353 (hh=ht): 2149716601081303960665650399258721969 (hh>ht): 19656438645792518015127863439276568110 (0.487340,0.050540,0.462121)
126(hh<ht): 41462593892666339990921377277811858188 (hh=ht): 4282285373105186235493617732141960711 (hh>ht): 39325712464463089639428656847988233965 (0.487390,0.050338,0.462272)
127(hh<ht): 82933710302031365514350931428118428640 (hh=ht): 8530682219042260845520404662961773086 (hh>ht): 78676790939395605371815967624803904002 (0.487441,0.050139,0.462421)
cost Ok(82.057µs)
页:
1
[2]