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?
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?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | jiangly | 3631 |
| 4 | Kevin114514 | 3574 |
| 5 | maroonrk | 3521 |
| 6 | strapple | 3515 |
| 7 | Radewoosh | 3461 |
| 8 | tourist | 3428 |
| 9 | turmax | 3378 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 140 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
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.