Wie hoch ist die zeitliche Komplexität, wenn bbb-Einträge ohne Ersatz von nnn-Einträgen einheitlich abgetastet werden?

Gegeben N Einträge nehme ich einheitlich ab B ersatzlose Einträge darunter.

Meine Frage ist, dass ich möchte, dass ein sehr schneller Algorithmus solche Dinge tut, und wie hoch ist seine zeitliche Komplexität? Ist die Konstante in der Zeitkomplexität Ö ( ) groß?

@spaceisdarkgreen Wenn man sich Ihren Link ansieht, ist diese Antwort zufällig genau die, die ich unten programmiert habe, außer dass er bei "max" beginnt und herunterzählt, während ich bei Null beginne und hochzähle. Und wie ich unten sagte, habe ich den Algorithmus einfach gegoogelt und implementiert, also ist es vielleicht kein großer Zufall. Vielleicht ist das die absolute Standardtechnik, die jeder findet, der danach googelt. Ich habe es vor einigen Jahren gegoogelt und kann mich nicht erinnern, was Google sonst noch ausgespuckt haben könnte. Aber ich erinnere mich, dass ich beeindruckt war, wie effizient es ist – viel besser, als Sie vielleicht naiv vermuten, dass das Problem gelöst werden könnte.

Antworten (1)

Ich bin sicher, Ihre Frage wurde gründlich recherchiert und veröffentlicht (haben Sie sie gegoogelt?). Ich persönlich habe nicht genau das benötigt, wonach Sie fragen, aber ich habe zufällige Permutationen von benötigt 1 … N , für die ich die folgende kleine Funktion geschrieben habe, basierend auf dem Googeln des Algorithmus, den sie implementiert ...

#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

Nun, ich denke, Sie würden nur das erste wollen B < N Eintragungen, Einnahme P [ 0 ] … P [ B − 1 ] wie Ihre Stichprobe ersatzlos. Und in diesem Fall, denke ich, könnten Sie die Schleife einfach anhalten B − 1 (statt bei N − 1 für die gesamte Permutation). Und dann ist die Komplexität eindeutig nur linear B , was meiner Meinung nach so gut ist, wie Sie es sich erhoffen können.

Wie hoch ist die zeitliche Komplexität, wenn bbb-Einträge ohne Ersatz von nnn-Einträgen einheitlich abgetastet werden?
AntwortenHierDatenschutz-Bestimmungen1y, 0v