尽管评论中已经回答了大部分问题，但我想指出一个我认为非常重要的细节。

关于复杂性，您可以提出几个问题：

• 找到某个数量的“最小/紧密”渐近复杂度是多少（在您的情况下，它是基尼指数）？
• 某个算法的渐近复杂度是多少（如果我们想要非常细粒度，甚至是它的实现）？

关于紧（）和上限（复杂性之间的差异，关于 SO 的以下问题可能很有用。我将使用表示法来回答这个问题；不过，使用也足够了。$\Theta(N)$$\mathcal O(N))$$\Theta$$\mathcal O$

现在，对于基尼指数，让我们考虑两个“算法”来找到所需的数量：变体：这将由您的问题中的公式准确描述，而变体由修改后的公式描述：$A$$B$

$$\text{Gini}_A(\mathbf{x}) = 1-2\sum_{k=1}^{N}\frac{\mathbf{x}(k)}{\color{red}{||\mathbf{x}||_1}}\frac{N-k+0.5}{N}\\ \text{Gini}_B(\mathbf{x}) = 1-\frac{2}{\color{red}{||\mathbf{x}||_1}}\sum_{k=1}^{N}\mathbf{x}(k)\frac{N-k+0.5}{N}$$

请注意，在算法中，我明确地将向量范数的计算移到求和之外，以表明它的计算只发生一次。现在，如果我们假设算法实际上计算了范数次（无缘无故），那么：$B$$||\mathbf{x}||_1$$A$$||\mathbf{x}||_1$ $N$

• 的复杂度为范数的计算发生次，其中一个范数计算是复杂度。$A$$\Theta(N^2).$$N$$\Theta(N)$
• 的复杂度是。首先在中计算范数，然后计算触及的每个元素的总和- 另一个和乘法和减法。$B$$\Theta(N)$$\Theta(N)$$\mathbf{x}$$\Theta(N)$$\Theta(1)$