Comment effectuer cette tâche dans O (1) (amorti)?

Je voulais juste confirmer avec quelqu'un que je suis sur la bonne voie avant de poursuivre. Le problème indique que lorsque je veux ajouter un nouvel élément à un tableau déjà FULL, je dois "développer le tableau dans O (1) (amorti)". Est-ce dire que chaque fois que j'insère un nouvel élément dans une liste complète, je devrais ajouter 5 éléments ou quelque chose comme ça, donc je n'ai pas besoin d'effectuer une expansion chaque fois qu'un nouvel élément est ajouté?Comment effectuer cette tâche dans O (1) (amorti)?

Source

2017-06-11 gabson

Oui, c'est l'idée de base. En supposant que l'expansion du tableau est juste une pénalité constante, ce serait 'O (1)'. –

Super, merci pour votre aide. – gabson

@TimBiegeleisen: Vous voulez dire non, non? L'idée de base est d'augmenter la taille d'une quantité proportionnelle à la taille actuelle, de ne pas l'augmenter par un nombre constant d'éléments, comme le propose l'OP. –

Est-ce à dire que chaque fois que je insérer un nouvel élément dans une liste complète que je devrais ajouter 5 éléments ou quelque chose comme ça, donc je ne dois pas effectuer une expansion chaque fois qu'un nouvel élément est ajouté?

Trier par. Mais toute constantes nombre de slots supplémentaires aura le même problème: même si vous avez seulement à copier vers un nouveau tableau toutes les cinq insertions, cela correspond toujours à O (n) temps par insertion, car O (ⁿ/) = O (n ). Au lieu de cela, vous devez ajouter un nombre d'emplacements proportionnel à la taille actuelle du tableau. La plus simple approche est de doubler la taille du tableau chaque fois que vous devez croître, ce qui équivaut en moyenne à O (n /_n) = O (1); mais l'augmenter de (disons) 50%, ou toute autre proportion constante, aurait le même effet.

Source

2017-06-11 02:43:15 ruakh

Notez que doubler conduit à un problème de vecteur itinérant. Supposons que vous commenciez avec 1k utilisé pour votre tableau. Vous allouez ensuite 2k, copiez et renvoyez le premier 1k au tas. Ensuite, vous allouez 4k, puis renvoyez 2k. Il y a maintenant 3k gratuit, et 4k utilisé. Prochain cycle 7k gratuit, 8k utilisé. Le stockage gratuit n'est jamais assez grand pour être recyclé pour une nouvelle allocation, donc la mémoire totale pour le processus est de 2x ce que vous utilisez réellement! Si vous utilisez la version 1.5, après quelques cycles, les données que vous avez libérées sont suffisamment grandes pour correspondre à l'allocation suivante. – Yakk

Bien sûr, il peut dépendre de votre compilateur/OS, mais la norme est de:

1. Allocate a new buffer with size 50 percent larger than the current buffer size 
2. Copy the data from the current buffer to the new buffer. 
3. Perhaps fiddle with addresses so the new buffer replaces the old buffer.

donc cela prend O (1)

Source

2017-06-11 02:42:45 Marichyasana

Votre étape 2 est O (N). – selbie

@selbie - oui, cette ** partie ** de l'algorithme est O (n), mais ce n'est pas fait à chaque fois; c'est fait pour chaque énième insertion (vaguement parlant), c'est pourquoi la complexité ** globale ** de l'ajout est O (1) amortie. C'est l'approche que 'std :: vector' utilise, par exemple. –

Oh, je vois ... Merci! – selbie

Comment effectuer cette tâche dans O (1) (amorti)?

Répondre

Questions connexes