$$F(S) = \sum_{i=1}^{|S|}\frac{p_{\alpha_i}}{1 - p_{\alpha_i}} \left( \prod_{j=1}^{|S|}(1-p_{\alpha_j})\right).$$
If one would like to use the search naively, the complexity will be of course large as $n!$. I want to say a simple variational argument is although simple but useful. But supposing adding one more element, deleting one element, or replacing one element, one can see quickly the description for this optimal subset is $\tau$ that
$$S := \{p_i\}_{1 \leq i \leq \tau}, \tau := \min \left\{n \in \mathbb{N}: \sum_{i=1}^\tau \frac{p_i}{1-p_i} \geq 1\right\}.$$
Thus the complexity is reduced to $O(n)$. So let us always think about the variational argument.
If one would like to use the search naively, the complexity will be of course large as $n!$. I want to say a simple variational argument is although simple but useful. But supposing adding one more element, deleting one element, or replacing one element, one can see quickly the description for this optimal subset is $\tau$ that
$$S := \{p_i\}_{1 \leq i \leq \tau}, \tau := \min \left\{n \in \mathbb{N}: \sum_{i=1}^\tau \frac{p_i}{1-p_i} \geq 1\right\}.$$
Thus the complexity is reduced to $O(n)$. So let us always think about the variational argument.
没有评论:
发表评论