When a problem has a time limit of 1 second per test case or anything for that matter, how can I calculate the expected runtime of my program in seconds or ms?
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 160 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | Dominater069 | 154 |
8 | awoo | 154 |
10 | luogu_official | 151 |
When a problem has a time limit of 1 second per test case or anything for that matter, how can I calculate the expected runtime of my program in seconds or ms?
Name |
---|
It comes with experience.
TheRe are MANy iNCompREheNsIBLe opTImiZAtIons iN MoDErN cPu and meMorY. FROm C++COdE TO aSSeMblY Is eNOUGH TO COnsuMe a peRsOn's lIfE. iT IS ALmOsT impOsSiblE To fIND A metHod tO accUrATeLY cALCuLAte tHE time ReQuIred FOr a PrOgram tO RuN.
a MoRe EfFECtivE metHoD Is To EStImATe tHe iNcreMEnTaL COMPLExItY, OR (WHEn THe iNcReMENTAl COmpLexIty IS DifFicult to CAlcUlATE) genERATE thE lArgEst dAta AND run IT lOcaLlY.
I think if the time complexity of your program if f(n), then you must have f(n) <= 10^9 to work. Thats a good heuristic anyways. So 10^5 you can use n * sqrt(n) or nlgn or n time complexity, or n= 10^4 you can use n^2, or n= 30 you can use 2^n (maybe, depends on constant factors). If n=10^9 you need linear time, or something very close to linear like maybe n *lg(lg(n)). More exact than that is just random stuff you learn. Like hashmaps are slow, so it might make a solution with right asymptotic performance not work still.
Almost all problems have time limit 1s or roughly that, so this heuristic works well.
This is a good comment except you use 1e9 instead of 1e8. I have never seen a linear algo work for 1e9, and if it does it's certainly the exception rather than the rule.
Even when you get something to a complexity that reaches something like 1e8 (like a n² dp for n = 10000) you need to be really careful about constant factors (recursive dps never work and sometimes the order in which you declare the states in your dp table matters, dp[n][m] might pass but dp[m][n] might not). Saying that checking for 1e9 is a good heuristic is crazy.
Hmmm. I think I agree with you. I am saying f(n) = 10^9 is an upper bound. Ie if its worse than that, forget it. However, it might not work even if f(n) = 10^9. I think I have done problems in linear time with n = 10^9. I can't find any right now though. Maybe I am wrong and am misremembering.
https://mirror.codeforces.com/blog/entry/12755
Here I see some people posting scripts to count number of operations on codeforces servers, and get 4 * 10^9 operations albeit with extremely simple code.
Maybe this will help you.