If you've got a known performance problem it's not premature. Knuths quote is the programming version of don't buy clothes for your baby before you've had sex for the first time.
There are some important distinctions though, which gets lost if one takes the quote at face value without much context. For example, I think one should strive to avoid O(n^2) loops and similar unless one is absolutely positively certain n will forever be bounded to some sane value.
My point being that O(n^2) code can make the application completely unusable, which makes it something more than a pure optimization problem.
(As an aside, some asexual people, who never had sex and are not interested in ever having sex, are still interested in adopting, and would buy clothes for their baby before having sex for the first time.)
There are some important distinctions though, which gets lost if one takes the quote at face value without much context. For example, I think one should strive to avoid O(n^2) loops and similar unless one is absolutely positively certain n will forever be bounded to some sane value.
My point being that O(n^2) code can make the application completely unusable, which makes it something more than a pure optimization problem.