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

How to find if your solution will cause Time exceeded error ?
Автор hari6988, 14 лет назад, По-английски

Hi,

Can someone tell me on what basis you decide that a naive solution will cause time exceeded error ? I have faced this problem quite a few times.

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

14 лет назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

You should know that an average cheking system can do(should I use do or make verb in this case?) about 10000000(10^7) simple operations per second.(For example, my PC can add 30000000 integers to each other in a second). So if you want to do something like this:
for (int i = 0; i < 100000; i++) for (int j = 0; j < 100000; j++) ....//do smth
it will definetely get TL(10^10 operations).
But if you want to sort an array of 100000 elements(100000 * log2(1000000) < 10^7), everything will be ok.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
The main method for this is formal complexity estimation, the one with O() notation. There are also smaller implementaion factors affecting performance, like cache efficiency, but the time limits are usually not very strict and asymptotically good solution is usually enough.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
You can also measure the time your program takes to run on the worst case(s). Usually try the big ones.
→ Ответить