How Important Do You Think Math Is To Programming? - Psychology, Philosophy, and Licenses
Users browsing this thread: 1 Guest(s)
|
|||
(19-04-2016, 09:21 AM)rain1 Wrote: ... Brute force does not mean exponential time. When you use a brute force algorithm, it just means you aren't taking advantage of the nature of the problem to avoid checking some solutions. For instance, a naive password cracking algorithm would be brute force; it would enumerate all possible passwords and check them one at a time. But that algorithm has linear complexity. An example of exploiting the nature of the problem to avoid checking all solutions is binary search. Say you have a sorted list and want to know if the list contains a certain element. You can do this by brute force in O(n), linear, time by starting at the beginning of the list and checking each one. Or you can exploit the nature of a sorted list and use binary search, which runs in O(logn) time. The takeaway is brute force has nothing to do with exponential time. I agree with rain1, algorithms complexity is probably the most useful math to know when it comes to being a programmer. But often just knowledge of how to find the big-oh notation of your program isn't good enough. You need to know lots of ways to solve lots of different problems in order to fix your code when it's taking too long to run. So I'd propose data structures as being important math to know as a programmer. The reason is that data structures tie heavily into the complexity and therefore the runtime of your program. One example I ran into recently is finding the longest common substring of two strings. If you take a brute force approach, you are stuck with an exponential time algorithm :( But it turns out there's a totally cool data structure that will reduce the complexity significantly. Store the strings in a suffix tree, and you get O(n) time and space once the tree is constructed. [1] I mention this last because it could be specific to the domains I've been exposed to recently, but numerical analysis and probability are great tools to have in your toolbelt. Numerical analysis comes into play when you are curve fitting, for example. Being able to map the probability of events that apply to your problem at hand can guide you in the design of your solution. I may write some posts on this stuff :) [1] https://www.cs.helsinki.fi/u/ukkonen/Suf...thFigs.pdf
They wrote down my brain
on a hard knot of space, You cannot turn me. |
|||
