为什么这个算法的 Big-O 是 N^2*log N

问题描述

从 a[0] 到 a[n-1] 填充数组 a:生成随机数，直到得到一个不在先前索引中的随机数.

Fill array a from a[0] to a[n-1]: generate random numbers until you get one that is not already in the previous indexes.

这是我的实现:

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;
}

我以为是 N^2，但显然是 N^2logN，我不确定何时考虑对数函数.

I thought it was N^2 but it's apparently N^2logN and I'm not sure when the log function is considered.

推荐答案

0 条目立即填充.1 条目有 1 - 1/n = (n - 1)/n 被随机数填充的概率.所以我们平均需要 n/(n - 1) 个随机数来填充第二个位置.一般来说，对于 k 条目，我们平均需要 n/(n - k) 个随机数，对于每个数字，我们需要 k 次比较检查它是否唯一.

The 0 entry is filled immediately. The 1 entry has probability 1 - 1 / n = (n - 1) / n of getting filled by a random number. So we need on average n / (n - 1) random numbers to fill the second position. In general, for the k entry we need on average n / (n - k) random numbers and for each number we need k comparisons to check if it's unique.

所以我们需要

n * 1/(n - 1) + n * 2/(n - 2) + ... + n * (n - 1)/1

平均比较.如果我们考虑和的右半部分，我们看到这半部分大于

comparisons on average. If we consider the right half of the sum, we see that this half is greater than

n * (n/2) * (1/(n/2) + 1/(n/2 - 1) + ... + 1/1)

分数之和已知为 Θ(log(n)) 因为它是一个 谐波系列.所以总和是Ω(n^2*log(n)).以类似的方式，我们可以将总和表示为 O(n^2*log(n)).这意味着我们平均需要

The sum of the fractions is known to be Θ(log(n)) because it's an harmonic series. So the whole sum is Ω(n^2*log(n)). In a similar way, we can show the sum to be O(n^2*log(n)). This means on average we need

Θ(n^2*log(n))

操作.

这篇关于为什么这个算法的 Big-O 是 N^2*log N的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！