Блог пользователя Mikemal

Time complexity.
Автор Mikemal, история, 21 месяц назад, По-английски

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?

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It comes with experience.

→ Ответить
»
21 месяц назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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.

→ Ответить
»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    21 месяц назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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://codeforces.me/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.

      → Ответить
»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Maybe this will help you.

→ Ответить