Ce n'est pas le travail à la maison de mon école. C'est mon propre travail à la maison et je suis des algorithmes d'auto-apprentissage.
dans Manuel de design d'algorithme , il y a une telle excise
4-25 suppose que le tableau A [1..n] n'a que des nombres de {1 ,. . . , N ^ 2} mais que, au plus, le journal de journal N de ces chiffres apparaissent jamais. Concevoir un algorithme qui trie un nombre sensiblement inférieur à O (n log n).
J'ai deux approches:
La première approche:
Fondamentalement, je veux compter le tri pour ce problème. Je peux d'abord analyser l'ensemble du tableau (O (N)) et mettre tous les nombres distincts dans une matrice de taille Loglogn (int [] k).
Appliquez ensuite le tri de comptage. Toutefois, lors de la configuration de la matrice de comptage (INT [] C), je n'ai pas besoin de définir sa taille comme n ^ 2, à la place, j'ai également défini la taille de LogLogn.
Mais de cette manière, lors de compter les fréquences de chaque numéro distinct, je dois numériser le tableau K pour obtenir l'index de cet élément (O (nloglogn) puis mettre à jour le tableau C.
La deuxième approche:
Encore une fois, je dois numériser l'ensemble de la matrice pour obtenir un tableau de numéros distinct K avec la taille Loglogn.
Ensuite, je viens de faire une sorte de trimbès, mais la partition est basée sur la médiane du tableau K (c'est-à-dire que chaque fois que le pivot est un élément de kary K), récursivement.
Je pense que cette approche sera la meilleure, avec O (nlogloglogn).
suis-je raison? ou il y a de meilleures solutions?
Des excès similaires existent dans le manuel design d'algorithme, tels que
4-22 montre que n entiers positifs dans la plage 1 à k peut être trié dans le temps O (N log K). Le cas intéressant est quand k << n.
4-23 Nous cherchons à trier une séquence S de N entiers avec de nombreuses duplications, de sorte que le nombre d'entiers distincts dans S est O (log n). Donnez un algorithme de délais de biche O
Mais fondamentalement pour toutes ces extractions, mon intuitif pensait toujours à compter le tri car nous pouvons connaître la plage des éléments et la plage est suffisamment courte de la longueur de l'ensemble de l'ensemble. Mais après plus de réflexion profondément, je suppose que les excès recherchent est la deuxième approche, non?
merci
4 Réponses :
Le tri de comptage est l'une des manières possibles:
first_part_of_number .
- Trier ce tableau en utilisant le tri de comptage par
first_part_of_number .
-
Les résultats sont sous forme (exemple pour n = 3)
(0, 2)
(0, 1)
(0, 1)
(2, 8)
(2, 6)
(2, 7)
(2, 6)
-
les diviser en groupes par first_part_of_number .
-
Dans cet exemple, vous aurez des groupes
(0, 2)
(0, 1)
(0, 1)
et
(2, 8)
(2, 6)
(2, 7)
(2, 6)
-
pour chaque numéro calcul x modulo n. permet de l'appeler second_part_of_number . Ajoutez ce numéro à chaque élément
(0, 2, 2)
(0, 1, 1)
(0, 1, 1)
et
(2, 8, 2)
(2, 6, 0)
(2, 7, 1)
(2, 6, 0)
-
Trier chaque groupe à l'aide de comptage Trier par second_part_of_number
(0, 1, 1)
(0, 1, 1)
(0, 2, 2)
et
(2, 6, 0)
(2, 6, 0)
(2, 7, 1)
(2, 8, 2)
-
combine maintenant tous les groupes et vous avez des résultats 1, 1, 2, 6, 6, 7, 8.
Complexité:
Vous n'utilisiez que compter uniquement les éléments <= N.
Chaque élément a participé à exactement 2 "sortes". La complexité globale est donc o (n).
mérite d'être mentionné: il s'agit en fait d'une variante de Seau de godet
Mise à jour: Après avoir écrit la réponse ci-dessous, @Nabb m'a montré pourquoi c'était incorrect. Pour plus d'informations, voir Brève entrée de Wikipedia sur õ et les liens de celui-ci. Au moins parce qu'il est encore nécessaire de prêter son contexte aux commentaires de @ Nabb et @ Blueeshift, et que toute la discussion reste intéressante, ma réponse originale est conservée, comme suit.
Permettez-moi d'offrir une réponse non conventionnelle: bien qu'il y ait effectivement une différence entre O (n * N) et O (n), il n'y a pas de différence entre O (n) et O (n * journal (n)). < / p>
Maintenant, bien sûr, nous savons tous que ce que je viens de dire est faux, n'est-ce pas? Après tout, divers auteurs concurrent que O (n) et O (n * journal (n)) diffèrent.
sauf qu'ils ne diffèrent pas.
si radical-semblant une position exige naturellement justification, alors considérez ce qui suit, puis constituez votre propre esprit.
mathématiquement, essentiellement, la commande m d'une fonction f (z) est telle que f (z) / (z ^ (m + epsilon) ) converge tandis que f (z) / (z ^ (m-epsilon)) diverge pour z de grandes grandeur et réel, positif epsilon < / em> d'une magnitude arbitraire. Les z peuvent être réels ou complexes, bien que nous avons dit epsilon doit être réel. Avec cette compréhension, appliquez la règle de l'hôpital vers une fonction de O (n * journal (n)) pour voir qu'il ne diffère pas dans l'ordre d'une fonction de O (n).
Je soutiendrais que la littérature informatique acceptée à l'heure actuelle est légèrement confondue sur ce point. Cette littérature finira éventuellement à affiner sa position dans la matière, mais elle n'a pas encore fait.
Maintenant, je ne m'attends pas à ce que vous êtes d'accord avec moi aujourd'hui. Ceci, après tout, est simplement une réponse à Stackoverflow - et qu'après que c'est comparé à un livre de science informatique publié, formellement révisé formellement par des pairs, à ne pas mentionner une Shelffull de tels livres? Vous ne devriez pas être d'accord avec moi aujourd'hui, ne prenez que ce que j'ai écrit sous-joint, réprimandez-le dans votre esprit ces prochaines semaines, consultez un ou deux des livres de sciences informatiques susmentionnés qui prennent l'autre position et constituent votre propre esprit. .
Incidemment, une implication contre-intuitive de la position de cette réponse est que l'on peut accéder à un arbre binaire équilibré dans O (1) temps. Encore une fois, nous savons tous que c'est faux, non? C'est censé être O (log (n)). Mais rappelez-vous: la notation O () n'a jamais été destinée à donner une mesure précise des demandes de calcul. Sauf si n est très important, d'autres facteurs peuvent être plus importants que la commande d'une fonction. Mais, même pour n = 1 million, journal (n) n'est que 20, comparé, par exemple, à SQRT (N), qui est 1000. Et je pourrais continuer dans cette veine.
Quoi qu'il en soit, donnez-lui une pensée. Même si, finalement, vous décidez que vous n'êtes pas d'accord avec moi, vous pouvez trouver la position intéressante néanmoins. Pour ma part, je ne suis pas sûr de la manière dont la notation O () est utile, c'est vraiment quand il s'agit de O (loger quelque chose).
@blueshift pose des questions intéressantes et soulève des points valides dans les commentaires ci-dessous. Je vous recommande de lire ses mots. Je n'ai pas vraiment beaucoup à ajouter à ce qu'il a à dire, sauf pour observer cela, car peu de programmeurs ont (ou ont besoin de) une mise à la terre solide dans la théorie mathématique de la variable complexe, le O (log (n)) La notation a probablement induit, littéralement des centaines de milliers de programmeurs de croire qu'ils atteignaient principalement des gains illusoires d'efficacité informatique. Rarement en pratique réduit O (n * log (n)) à O (n) vous achète vraiment ce que vous pourriez penser qu'il vous achète, à moins que vous n'ayez une image mentale claire de la façon dont le logarithme est incroyablement lent le logarithme. Alors que la réduction de O (n) même à O (sqrt (n)) peut vous acheter beaucoup. Un mathématicien aurait dit à l'informatique scientifique il y a cette décennie, mais l'informatique n'a pas écouté, était pressé, ou n'a pas compris le point. Et tout va bien. Cela ne me dérange pas. Il y a beaucoup de points sur d'autres sujets que je ne comprends pas, même lorsque les points m'ont soigneusement expliqué. Mais c'est un point que je crois que je suis arrivé à comprendre. Fondamentalement, il s'agit d'un point mathématique et non d'un point informatique, et c'est un point sur lequel je suis arrivé côté avec Lebedev et les mathématiciens plutôt qu'avec Knuth et les informaticiens. C'est tout.
Jusqu'à ce que vous obteniez cela publié, je pense que je vais rester avec Knuth.
@blueshift: C'est vrai. Eh bien, j'essaierai peut-être de le publier un jour, mais ce n'est pas facile (pas plus que ce n'est que) de pousser une position contradictoire après des pairs qui ont un investissement de décennies à la position établie de Knuth. Et, après tout, la position de Knuth n'est pas une mauvaise. La position de Knuth est intéressante. Je pense juste que ça se trompe.
Je ne vois pas comment affirmant que 1 million = 20 millions a du sens ou est utile.
@blueshift: La commande est un concept, et c'est le concept qui est utile dans la conception initiale d'algorithmes. Bien sûr, 1 million et 20 millions ne sont pas les mêmes, comme vous le dites.
Big O Notation est un concept formellement défini et votre définition n'est pas la définition acceptée (je pense que vous pouvez être intéressé par õ).
@NABB: Votre correction est acceptée. Je modifie ma réponse maintenant.
Je vais trahir mes connaissances limitées de la complexité algorithmique ici, mais:
N'aurait-il pas de sens de scanner la matrice une fois et de construire quelque chose comme un arbre à équilibrer? Comme nous savons que le nombre de nœuds dans l'arborescence ne deviendra que (log N), il est relativement bon marché (?) Pour trouver un numéro à chaque fois. Si un numéro de répétition est trouvé (probablement) un compteur dans ce nœud est incrémenté. Ensuite, pour construire le tableau de tri, lisez l'arbre dans l'ordre.
Peut-être que quelqu'un peut commenter la complexité de cela et des défauts.
En ce qui concerne la question de la complexité: le faire est O (nlogloglogn) , c'est la même idée que je suggère dans ma solution ["Utiliser une carte au lieu d'un tableau"] - Cette solution utilise une arborescence Mise en œuvre de la carte.
Nous ne pouvons que créer une carte de hachage stockant chaque élément comme clé et sa fréquence comme valeur.
Trier cette carte dans maintenant Scannez la carte de hachage et ajoutez des éléments au nouveau nombre de fois de fréquence de tableau. Comme: journal (n) * journal (N)) TIME (code> klogk) en utilisant n'importe quel algorithme de tri.
Nous pourrions utiliser la structure de la BST de la taille du journal des journaux de taille des éléments Pourquoi - nous voulons trier sur des éléments moindres pour obtenir une heure d'exécution plus petite (je ne tiens pas à compter le tri, car il va prendre trop d'espace que mon tableau d'origine) nous pouvons maintenir compteur à chaque nœud pour gérer les duplicates T (n) = O (nombre d'éléments * hauteur de la BST) = O (n * journal journal de journal n) Comment prenez-vous de compter une éventail de format journal de journal N ^ 2