發表新討論
#18235: 複雜度


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

學校 : 國立臺灣師範大學附屬高級中學
編號 : 61090
來源 : [220.135.116.184]
最後登入時間 ：
2024-04-01 14:01:32
e284. 放暑假了!!!!! -- π | From: [220.135.116.184] | 發表日期 : 2019-06-29 13:33

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

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

 
#18236: Re:複雜度


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

學校 : 臺北市私立延平高級中學
編號 : 83268
來源 : [203.72.178.1]
最後登入時間 ：
2023-10-30 13:02:50
e284. 放暑假了!!!!! -- π | From: [114.42.214.29] | 發表日期 : 2019-06-29 13:46

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

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


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

但時間不如預期

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

 
#18238: Re:複雜度


314159265358979323846264338327 ... (少年π)

學校 : 臺北市私立延平高級中學
編號 : 69058
來源 : [223.137.74.225]
最後登入時間 ：
2024-04-18 19:26:56
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