Time complexity - Codeforces

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

Time complexity

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

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

time complexity

zscoder
10 лет назад
9

Комментарии (9)

Написать комментарий?

Nezzar

10 лет назад, # |

← Rev. 2 →

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)

→ Ответить

Dixtosa

10 лет назад, # ^ |

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

→ Ответить

msm_

10 лет назад, # ^ |

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.

→ Ответить

Dixtosa

10 лет назад, # ^ |

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

→ Ответить

Xellos

10 лет назад, # ^ |

Almost everything you mentioned should run longer than 10s, especially $\text{[math]}$ for N > 10¹². Just the O(N³) and O(N⁵) are possible, if those are dynamics with low constants.

For O(2^N), anything above N = 20 requires optimization. If N > 10⁸, you should probably try $\text{[math]}$ , but there are still peculiar complexities like $\text{[math]}$ .

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

→ Ответить

Dixtosa

10 лет назад, # ^ |

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>

→ Ответить