Is it possible to create an algorithm-aware optimizer?
Actually, optimizing compilers do that kind of things. I am for
example thinking of the work of Robert Paige at NYU. The problem is of
course to identify situations where a given type of transformation may be useful.
That require identifying computational structures, and knowing some of
the algebraic properties of the data being manipulated.

A classical example, very simple, is the strength-reduction in
loops, where you replace a product by a sum. It usually does not change
much the complexity (see more below), but can effectively speed up your algorithm, at
the cost of one extra variable. This is a special case of finite
differencing techniques.

I think you should find example in the litterature on high-level
optimization, which is quite different from peep-hole optimization in
the code generation process. See the two wikipedia article for various types of code optimization.

Regarding the identification of such situations, they can sometimes be
found by formal analysis of program. It can also help to make them
more apparent by using very high-level abstractions in the programming
process.

Many such transformations improve the program without changing the
complexity. But it much depends on what complexity you are considering
and what is a unit operation.

For example if you consider arithmetics of unbounded integers,
addition has linear cost, while multiplication has a higher cost
(quadratic in the naive case). Using reduction in strength in loops
will reduce complexity.

I unfortunately do not remember more spectacular cases.

There is also some significant litterature on program transformations, with a variety of techniques that started in the 1970ies. Some transformations may not bring much by themselves, but may enable other transformations. Pattern matching in equational algebras is one way of identifying possible tranformations that has been considered. This may be one reason why very high level abstractions can help the process.