Est-il possible de trouver le nombre de triangles qui peuvent être formés à partir d'une liste de longueurs de mieux que (n choisir 3) le temps?

Cela concerne un problème plus important sur lequel je travaille.Est-il possible de trouver le nombre de triangles qui peuvent être formés à partir d'une liste de longueurs de mieux que (n choisir 3) le temps?

Par exemple, disons que l'on nous donne une liste

9 5 6 1

Les triangles possibles auraient côtés de longueur

(9,5,6) 
(9,6,1) 
(9,5,1) 
(5,6,1)

et ceux qui sont valides (par l'inégalité triangulaire) sont

(9,5,6) 
(5,6,1)

Est-il possible? pour trouver ceux valables dans mieux que O(n choose 3) temps?

Source

2016-10-04 Deadly Nicotine

@Deadly nicotine, ce que vous entendez par O (n choisir 3), est-il O (n^3)? –

@Abdenaceur Lichiheb Il parle d'un coefficient binomial –

@AbdenaceurLichiheb Oui, désolé. Je voulais dire qu'il y a N choisir 3 telles possibilités, mais l'algorithme de force brute pour trouver ces possibilités est en effet O (N^3) –

En cas général, la réponse est pas: imaginez que vous êtes donné

1, 1 - ε, 1 - 2 * ε, ..., 1 - (n - 1) * ε

Dans ce cas très toutes les combinaisons de 3 articles

n * (n - 1) * (n - 2)/6 = O(n**3)

sont distincts et faire triangles valides et vous avez O(n**3) complexité juste à énumérer (et sortie) eux

Source

2016-10-04 15:06:33

Non. Vous pouvez avoir un ensemble d'entrées arbitrairement grand où chaque triplet est un triangle valide.

Source

2016-10-04 15:06:54 Dave

Commencez par trier votre liste. Maintenant, au lieu de faire une recherche O (n^3) complète, il suffit de rechercher une paire de points dans O (n^2) et de trouver le troisième point (peut-être plus d'un point, donc vous devez vérifier pour la limite inférieure et supérieure) en faisant une recherche binaire.

Donc dans l'ensemble de la nouvelle complexité est O (n^2 log (n))

Source

2016-10-04 15:11:42

oui, mais c'est juste les compter, au cas où vous voulez que les triples réels générés, le pire des cas est toujours 'O (n^3)', parce que vous devez générer en quelque sorte la sortie – cobarzan

En fait, je ne suis pas sûr que fonctionne, étant donné qu'il peut y avoir des répétitions .. –

@cobarzan, ouais vous avez raison, bien sûr, je suis juste donné le nombre de triangles, mais si vous avez besoin des triples réels, alors il est O (n^3), mais toujours considéré comme une optimisation locale. –

Est-il possible de trouver le nombre de triangles qui peuvent être formés à partir d'une liste de longueurs de mieux que (n choisir 3) le temps?

Répondre

Questions connexes