Hacker News new | comments | show | ask | jobs | submit login

Those depend a lot on the context. Firstly, the complexity for the arithmetic operations you listed mostly only matters if you are working with big numbers (something that is not very common to be a bottleneck). Factorization doesn't have a polynomial algorithm so I don't see why the complexity matters anyway (its still going to take longer than your lifetime with hard inputs anyway). As for linear systems, it depends a lot on your input and the problem you want to solve. If we talk about the Simplex algorithm that most people use, empirically it takes around cubic time but its still an open problem to find a base-choide heuristic that does not have pathological exponential worst case performance. In addition to that, many important problems are modeled as linear programs but will have extra special structure that let them be solved with more efficient algorithms.

Finally, you got me when it comes to the numerical stuff (eigenvectors and matrix inversion). I haven't looked into that in a while.




> In addition to that, many important problems are modeled as linear programs but will have extra special structure that let them be solved with more efficient algorithms.

To specify: Those more efficient algorithms can surprisingly often be expressed as variants of the simplex method, too.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: