Je ne vois pas pourquoi le tri MSD Radix est théoriquement aussi efficace que le tri Radix LSD

Question

Voici le pseudocode pour le tri Radix LSD à partir de http://www.cs.princeton.edu/~rs/algsds07/18radixsort.pdf

   public static void lsd(String[] a)
   {
        int N = a.length;
        int W = a[0].length;
        for (int d = W-1; d >=0; d--)
        {
             int[] count = new int[R];
             for(int i = 0; i < N; i++)
                   count[a[i].charAt(d) + 1]++;
             for(int k = 1; k < 256; k++)
                   count[k] += count[k-1];
             for(int i = 0; i < N; i++)
                   temp[count[a[i].charAt(d)]++] = a[i];
             for(int i = 0; i < N; i++)
                   a[i] = temp[i];
        }
   }

Je suppose que par 256, ils signifient $ r $. Nous avons une boucle simple pour la simple Quoi, donc c'est le pire des cas et les meilleures performances de cas en même temps. Les exigences de l'espace sont $ theta (n + r) $

Voici le pseudocode de MSD:

    public static void msd(String[] a)
    { 
        msd(a, 0, a.length, 0); 
    }

    private static void msd(String[] a, int lo, int hi, int d)
    {
        if (hi <= lo+1) return;
        int[] count = new int[256+1];
        for (int i = 0; i < N; i++)
             count[a[i].charAt(d)+1]++;
        for (int k = 1; k < 256; k++)
             count[k] += count[k-1];
        for (int i = 0; i < N; i++)
             temp[count[a[i].charAt(d)]++] = a[i];
        for (int i = 0; i < N; i++)
             a[i] = temp[i];
        for (int i = 0; i < 255; i++)
             msd(a, l+count[i], l+count[i+1], d+1);
   }

Puisque la récursivité, nous cesserons de récurer après $ W $ dans le pire des cas, la complexité de l'espace devient $ theta (n + wr) $

Mais qu'en est-il du temps? Juste de l'espace lui-même, il semble que MSD soit en fait assez mauvais. Que pouvez-vous dire à propos de l'heure? Pour moi, il semble que vous devrez dépenser des opérations $ R $ pour chaque nœud de votre arbre de récursivité et également des opérations $ N $ par tous les niveaux. Donc, le temps est $ theta (nw + r * montantofnodes) $.

Je ne vois pas comment et pourquoi MSD serait jamais préféré dans la pratique compte tenu de ces limites de temps. Ils sont assez horribles, mais je ne sais toujours pas si j'obtiens les limites de temps d'une manière correcte, par exemple je n'ai aucune idée de la taille amountOfNodes..

Gardez à l'esprit que j'aimerais que l'analyse soit en termes de R et N. Je sais que dans la pratique, R est généralement petit, donc c'est juste une constante, mais je ne suis pas intéressé par ce scénario, car j'aimerais voir combien R affecte-t-il également les performances.

J'ai demandé à un sorte de question similaire Hier, mais j'ai reçu des réponses, je pense que la raison en était parce que ma question n'était pas bien structurée, donc je pourrais supprimer cette question si les administrateurs le voulaient. Merci d'avance!