Résumé : Micro-organisms expend energy moving through complex media. While propulsion speed is an important property of locomotion, efficiency is another factor that may determine the swimming gait adopted by a micro-organism in order to locomote in an energetically favorable manner. The efficiency of swimming in a Newtonian fluid is well characterized for different biological and artificial swimmers. However, these swimmers often encounter biological fluids displaying shear-thinning viscosities. Little is known about how this nonlinear rheology influences the efficiency of locomotion. Does the shear-thinning rheology render swimming more efficient or less? How does the swimming efficiency depend on the propulsion mechanism of a swimmer and rheological properties of the surrounding shear-thinning fluid? In this work, we address these fundamental questions on the efficiency of locomotion in a shear-thinning fluid by considering the squirmer model as a general locomotion model to represent different types of swimmers. Our analysis reveals how the choice of surface velocity distribution on a squirmer may reduce or enhance the swimming efficiency. We determine optimal shear rates at which the swimming efficiency can be substantially enhanced com- pared with the Newtonian case. The non-trivial variations of swimming efficiency prompt questions on how micro-organisms may tune their swimming gaits to exploit the shear-thinning rheology. The findings also provide insights into how artificial swimmers should be designed to move through complex media efficiently.