Advantage of using FIR Polyphase Decimator over just computing FIR output every D samples

Let's say you want to implement an FIR filter $h[k]$ with $L$ taps and downsample the output:

$v[k] = x[k] * h[k]$

$y[m] = v[kD]$

The "naive" way would be to compute all the samples of $v[k]$, then compute $y[m]$. This should have complexity of $O(LD)$ to process a block of $D$ samples.

The "less naive" way would be to just compute every $D^{th}$ sample of $y[m]$ directly:

$y[m] = v[mD] = \sum_{l = 0}^{L-1} x[mD - l] h[l]$

This should have a complexity of $O(LD/D) = O(L)$ to process a block of $D$ samples.

The "smart" way, according to everything I read (e.g. Proakis & Manolakis Digital Signal Processing: Principles, Algorithms, and Applications, 4th ed. p.771, also here), is to use a polyphase filter/decimator.

This seems to have the same computational burden: every $D^{th}$ timestep, you are computing the output of $D$ filters, each of which has $L/D$ taps, for a total complexity of roughly $O(DL/D) = O(L)$.

Is my analysis correct? If so, what is the advantage of using a polyphase decimator if the "skip $D$" method has the same complexity and is much easier to implement?

Yes, they have the same complexity because they are exactly the same. By calculating every $D^{th}$ sample you'll see there are $D$ filters needed - each with $L/D$ taps.
One advantage of the polyphase filter is when hardware resources are limited. The polyphase approach replaces a $L$ tap filter with $N$ filter sets of $L/N$ taps. Once you've done that you can just use a single $L/N$ filter set and swap coefficients.