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

Автор zscoder, 11 лет назад, По-английски

I'm just wondering, how fast should my algorithm be in order to avoid TLE (Time Limit Exceeded)?

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

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Difficult to tell, around 10^8

for N=20, O(2^N) is nice

for N=30, O(N^5)

for N=100, O(N^3)

for N=1000, O(N^2)

for N=100000, O(N lg N)

for N>10^12, you may need to consider O(1)/O(lg N)

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

    Exactly, it depends highly on basic operations you use. for example % (mod) is worth nearly dozens of if operations...

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

      That's not true — integer modulo is fast (exactly as fast as division, to be exact, and integer division is fast nowadays) and floating point modulo is not used that much.

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

        Well, I had a case where I multiplied 100x100 matrices and in the innermost loop I used integer modulo (long long to be precise) and when I put it in the second loop (from the 3rd one) the time decreased by 1 sec

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

    Almost everything you mentioned should run longer than 10s, especially for N > 1012. Just the O(N3) and O(N5) are possible, if those are dynamics with low constants.

    For O(2N), anything above N = 20 requires optimization. If N > 108, you should probably try , but there are still peculiar complexities like .

    It's hard to say anything in general, because there are many subtle differences. You really find out what you can afford by experience.

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

      Actually, CF's comment system messed it up. He didn't separate the list with commas rather he split it with newlines which are unfortunately not seen unless you type <br>

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

        Ow... I thought it was separated by commas. That's why I always use Preview before posting.

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

        that means i need to type two new lines to see the actual new line? orz

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

Thanks!