Какова временная сложность при равномерной выборке записей bbb без замены записей nnn?

Я уверен, что ваш вопрос был тщательно изучен и опубликован (вы искали его в Google?). Мне лично не нужно именно то, о чем вы просите, но мне нужны случайные перестановки$1\ldots n$, для которого я написал следующую маленькую функцию, основываясь на алгоритме, который она реализует...

#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

Теперь, я думаю, вы просто хотите, чтобы первый$b<n$записи, взятие$p[0]\ldots p[b-1]$как ваш случайный образец без замены. И в этом случае, я думаю, вы могли бы просто остановить цикл на$b-1$(вместо на$n-1$для всей перестановки). И тогда сложность явно просто линейна в$b$, что, я полагаю, в значительной степени настолько хорошо, насколько вы можете надеяться.