¿Cuál es la complejidad del tiempo cuando se muestrean uniformemente las entradas bbb sin reemplazo de las entradas nnn?

Estoy seguro de que su pregunta ha sido investigada y publicada a fondo (¿la buscó en Google?). Personalmente, no he necesitado exactamente lo que estás pidiendo, pero he necesitado permutaciones aleatorias de$1\ldots n$, para lo cual escribí la siguiente pequeña función, basada en buscar en Google el algoritmo que implementa...

#include <stdio.h>
#include <stdlib.h>
/* ==========================================================================
 * Function:    int permutation ( int seed, int n, int *p )
 * Purpose:     Returns p[0]...p[n-1] containing 1...n arranged randomly
 * --------------------------------------------------------------------------
 * Arguments:   seed (I)    int optionally containing seed for srandom(),
 *                          if 0 or negative, srandom() not called
 *              n (I)       int containing rank of permutation
 *              p (O)       &int returning 1...n arranged randomly
 * Returns:     ( int )     n=success, 0=failure
 * --------------------------------------------------------------------------
 * Notes:     o
 * ======================================================================= */
/* --- entry point --- */
int permutation ( int seed, int n, int *p ) {
  /* --- Allocations and Declarations --- */
  int   i=0;                /* p[] index */
  /* --- Initialization --- */
  if ( n<1 || p==NULL ) { n=0; goto end_of_job; } /* input error */
  if ( seed > 0 ) srandom(seed);    /* initialize random() */
  for ( i=0; i<n; i++ ) p[i] = i+1; /* initialize p[0...n-1] = 1...n */
  /* ---
   * Generate random permutation
   * ------------------------------ */
  for ( i=0; i<n-1; i++ ) {
    int j = i + ((random())%(n-i)); /* random i <= j <= n-1 */
    int pi = p[i];          /* swap p[i] <--> p[j] */
    p[i] = p[j];            /* p[i] = p[j] */
    p[j] = pi; }            /* p[j] = p[i] */
  end_of_job:
    return ( n );           /* back to caller */
  } /* --- end-of-function permutation() --- */

/* ---
 * Test Driver
 * -------------- */
#if defined(TESTDRIVE)
int main ( int argc, char *argv[] ) {
  int   n    = (argc>1? atoi(argv[1]) : 16 ), /* rank of permutation */
        seed = (argc>2? atoi(argv[2]) : 7654321 ); /* srandom() seed */
  int   permutation(), p[9999],     /* random permutation of 1...n */
        i=0;                        /* p[] index */
  if(n<0)n=16;  if(n>999)n=999;     /* sanity check */
  permutation(seed,n,p);            /* generate permutation */
  for ( i=0; i<n; i++ )             /* print results */
    printf("%5d%s",p[i],((i+1)%10==0||i==n-1?"\n":", "));
  } /* --- end-of-function main() --- */
#endif

Ahora, creo que solo querrías el primero$b<n$entradas, tomando$p[0]\ldots p[b-1]$como su muestra aleatoria sin reemplazo. Y en ese caso, creo que podrías simplemente detener el ciclo en$b-1$(en lugar de en$n-1$para toda la permutación). Y luego la complejidad es claramente lineal en$b$, que supongo que es tan bueno como se puede esperar.