發表新討論
#18235: 複雜度


icube (!@#$%^&*()_+)

e284. 放暑假了!!!!! -- π | From: [220.135.116.184] | 發表日期: 2019-06-29 13:33

出題者原來是想卡掉 O(logn) 的做法

但輸入本身就會花上 O(logn) 的時間吧？

#18236: Re:複雜度


ufve0704 (爬 我爬 我爬爬爬 有排行榜這種東西就是要爬 爬過我上面的那...)

e284. 放暑假了!!!!! -- π | From: [114.42.214.29] | 發表日期: 2019-06-29 13:46

出題者原來是想卡掉 O(logn) 的做法

但輸入本身就會花上 O(logn) 的時間吧？


照理講我的時間複雜度是O(1)

但時間不如預期

而我的字為甚麼便這麼大?

#18238: Re:複雜度


314159265358979323846264338327 ... (少年π)

e284. 放暑假了!!!!! -- π | From: [223.140.236.11] | 發表日期: 2019-06-29 13:58

出題者原來是想卡掉 O(logn) 的做法

但輸入本身就會花上 O(logn) 的時間吧？


照理講我的時間複雜度是O(1)

但時間不如預期

而我的字為甚麼便這麼大?

精確來說,輸入花的時間是O(log10n),而若用建表或除法的運算時間是O(log2n)
如果用位元運算,運算時間是O(1),所以總共單筆測資的時間是:

O(log10n+log2n)以及O(log10n+1)(如果算法有錯請告知),本來以為5*10^6筆測資就足以區分差距,但實測卻不是如此,只好調時限...

ZeroJudge Forum