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.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
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.
gerasimovd
|
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.
→
Ответить
|
wil93
|
14 лет назад,
#
^
|
0
@Dmitry: It is O(n*log2(n)), not O(n^log2(n))
→
Ответить
|
gerasimovd
|
14 лет назад,
#
^
|
0
yep, just a mistake :) fixed
→
Ответить
|
al13n
|
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.
→
Ответить
|
MciprianM
|
14 лет назад,
#
|
0
You can also measure the time your program takes to run on the worst case(s). Usually try the big ones.
→
Ответить
|
Название |
---|