4 ms·

Does everyone else feel like optimal/efficient algorithms are _significantly_ easier to intuit once you know the achievable complexity? My initial guess was tha

Does everyone else feel like optimal/efficient algorithms are _significantly_ easier to intuit once you know the achievable complexity? My initial guess was that this algorithm would be n log n, but once I read that the solution space was linear, I instantly came up with some linear approaches.

pizza 3y ago
Yes, maybe, since you can start working from the little pieces up to the big pieces, rather than the other way round. When you first see it, there could be all kinds of potential loci of interest being thrown at your face: the individual nodes, the neighbors of the nodes, the branching, the directionality, the depth of the thing, etc. so it takes you striking down the details you pick to not think about . So you start off with the biggest description of the possible solution space, unless you are trained seriously enough to just ‘see the answer’ without blinking to that first question of what to focus on. But if you get the complexity before hand, well that indexes quite swiftly into the potential domain spaces.
Karliss 3y ago
It's quite common during competitive programming (algorithms and datastructure). In many of the of contests your given input size constraints and time limit. Knowing that helps you narrow down which approaches or tools you shouldn't even try because they would be too slow, or when to stop because you came up with something good enough. In few contests that don't give precise input limits, it adds extra challenge. And if your idea for the optimal efficiency is wrong, you have not only wasted time implementing wrong solution, but might also get a penalty score for each failed submission. One of the worst feelings is when you see that your submission got time limit on something like test 87, and you are unsure whether it's due to having wrong asymptotic complexity or whether you have correct algorithm but just implemented it slightly too inefficiently and it only needs a little bit of minor optimizations to pass.

pizza 3y ago

Yes, maybe, since you can start working from the little pieces up to the big pieces, rather than the other way round. When you first see it, there could be all kinds of potential loci of interest being thrown at your face: the individual nodes, the neighbors of the nodes, the branching, the directionality, the depth of the thing, etc. so it takes you striking down the details you pick to not think about . So you start off with the biggest description of the possible solution space, unless you are trained seriously enough to just ‘see the answer’ without blinking to that first question of what to focus on. But if you get the complexity before hand, well that indexes quite swiftly into the potential domain spaces.

Karliss 3y ago

It's quite common during competitive programming (algorithms and datastructure). In many of the of contests your given input size constraints and time limit. Knowing that helps you narrow down which approaches or tools you shouldn't even try because they would be too slow, or when to stop because you came up with something good enough. In few contests that don't give precise input limits, it adds extra challenge. And if your idea for the optimal efficiency is wrong, you have not only wasted time implementing wrong solution, but might also get a penalty score for each failed submission. One of the worst feelings is when you see that your submission got time limit on something like test 87, and you are unsure whether it's due to having wrong asymptotic complexity or whether you have correct algorithm but just implemented it slightly too inefficiently and it only needs a little bit of minor optimizations to pass.