Pourquoi le Big-O de cet algorithme N ^ 2 * log N

Remplissez le tableau a de [0] à [n-1]: générez des nombres aléatoires jusqu’à ce que vous en obteniez un qui ne figure pas déjà dans les index précédents.

Ceci est ma mise en œuvre:

public static int[] first(int n) { int[] a = new int[n]; int count = 0; while (count != n) { boolean isSame = false; int rand = r.nextInt(n) + 1; for (int i = 0; i < n; i++) { if(a[i] == rand) isSame = true; } if (isSame == false){ a[count] = rand; count++; } } return a; }

Je pensais que c’était N ^ 2 mais c’est apparemment N ^ 2logN et je ne suis pas sûr de savoir quand la fonction de journalisation est prise en compte.

L’entrée 0 est remplie immédiatement. L’entrée 1 a une probabilité de 1 - 1 / n = (n - 1) / n d’être remplie par un nombre aléatoire. Nous avons donc besoin en moyenne de n / (n - 1) nombres aléatoires pour remplir la deuxième position. En général, pour l’entrée k nous avons besoin en moyenne de n / (n - k) nombres aléatoires et pour chaque nombre, nous avons besoin de k comparaisons pour vérifier si elle est unique.

Alors nous avons besoin

n * 1 / (n – 1) + n * 2 / (n – 2) + … + n * (n – 1) / 1

comparaisons en moyenne. Si l’on considère la moitié droite de la sum, on voit que cette moitié est supérieure à

n * (n / 2) * (1 / (n / 2) + 1 / (n / 2 – 1) + … + 1/1)

On sait que la sum des fractions est Θ(log(n)) car il s’agit d’une série d’harmoniques . La sum totale est donc Ω(n^2*log(n)) . De la même manière, nous pouvons montrer que la sum est O(n^2*log(n)) . Cela signifie en moyenne que nous avons besoin

Θ (n ^ 2 * log (n))

opérations.

Ceci est similaire au problème Collecteur de coupons. Vous choisissez parmi n éléments jusqu’à ce que vous en obteniez un que vous n’avez pas déjà. En moyenne, vous avez O (n log n) tentatives (voir le lien, l’parsing n’est pas anodine). et dans le pire des cas, vous examinez n éléments pour chacune de ces tentatives. Cela conduit à une complexité moyenne de O (N ^ 2 log N)

L’algorithme que vous avez n’est pas O(n^2 lg n) parce que l’algorithme que vous avez peut boucler indéfiniment et ne pas finir. Imaginez lors de votre premier passage, vous obtenez une valeur $ X $ et lors de chaque passage suivant, en essayant d’obtenir la deuxième valeur, vous continuez d’obtenir $ X $ pour toujours. Nous parlons le pire des cas ici, après tout. Cela ferait une boucle pour toujours. Donc, comme votre pire cas ne se termine jamais, vous ne pouvez pas vraiment parsingr.

Au cas où vous vous le demandiez, si vous savez que n est toujours à la fois la taille du tableau et la limite supérieure des valeurs, vous pouvez simplement faire ceci:

 int[] vals = new int[n]; for(int i = 0; i < n; i++) { vals[i] = i; } // fischer yates shuffle for(int i = n-1; i > 0; i--) { int idx = rand.nextInt(i + 1); int t = vals[idx]; vals[idx] = vals[i]; vals[i] = t; }

Une boucle, une boucle en arrière. O(n) . Simple.

Si je ne me trompe pas, la partie log N vient de cette partie:

 for(int i = 0; i < count; i++){ if(a[i] == rand) isSame = true; }

Notez que j'ai changé n pour count car vous savez que votre tableau ne count éléments sur chaque boucle.