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.
# | User | Rating |
---|---|---|
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 |
# | User | Contrib. |
---|---|---|
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 years ago,
#
|
←
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.
→
Reply
|
wil93
|
14 years ago,
#
^
|
0
@Dmitry: It is O(n*log2(n)), not O(n^log2(n))
→
Reply
|
gerasimovd
|
14 years ago,
#
^
|
0
yep, just a mistake :) fixed
→
Reply
|
al13n
|
14 years ago,
#
|
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.
→
Reply
|
MciprianM
|
14 years ago,
#
|
0
You can also measure the time your program takes to run on the worst case(s). Usually try the big ones.
→
Reply
|
Name |
---|