Non riesco a capire perché MSD Radix è teoricamente efficiente come LSD Radix Ordine

Question

Ecco lo pseudocodice per l'ordinamento di radix LSD da 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];
        }
   }

Immagino che per 256 significano $ r $. Abbiamo un ciclo semplice, quindi il tempo è $ theta (w (r+n)) $ Il motivo per cui uso $ theta $ è perché il limite è stretto, questo è quante operazioni farai, non importa Cosa, quindi è la peggiore prestazione del caso e del miglior caso allo stesso tempo. I requisiti di spazio sono $ theta (n+r) $

Quello che segue è lo pseudocodice di 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);
   }

Dalla ricorsione smetteremo di ricorrere dopo i livelli di $ w $ nel caso peggiore, la complessità spaziale diventa $ theta (n + wr) $

Tuttavia, che ne dici il tempo? Solo dallo spazio stesso, sembra che MSD sia in realtà piuttosto negativo. Cosa puoi dire del tempo? Per me sembra che dovrai spendere operazioni $ R $ per ogni nodo nel tuo albero di ricorsione e anche operazioni $ n $ per ogni livello. Quindi il tempo è $ theta (NW + r*importofnodes) $.

Non vedo come e perché MSD sarebbe mai preferito in pratica dati questi limiti di tempo. Sono piuttosto orribili, ma non sono ancora sicuro di avere i limiti del tempo in modo corretto, ad esempio non ho idea di quanto sia grande amountOfNodes..

Tieni presente che vorrei che l'analisi fosse in termini di R e N. So che in pratica R è di solito piccola, quindi è solo una costante, ma non sono interessato a questo scenario, dal momento che mi piacerebbe vedere quanto R influenza anche le prestazioni.

Ho chiesto a tipo di domanda simile Ieri, ma ho ricevuto qualsiasi risposta, penso che il motivo fosse perché la mia domanda non era ben strutturata, quindi avrei potuto rimuovere questa domanda se gli amministratori volessero. Grazie in anticipo!