J'ai donc un problème avec une tâche.

Vous avez donné une séquence de nombres et n opérations dans chacun, il y a deux nombres (index dans cette séquence donnée).

Vous devez vérifier si la séquence après chaque opération sera triée ou non. (Chaque opération est appliquée).

Mon problème est que ma solution est trop lente. Cela fonctionne en O (n ^ 2). (Je fais juste un swap et j'utilise is_sorted de c ++ 11). Comment le rendre plus rapide?

Merci d'avance

0
Polish IT Guy 27 nov. 2017 à 21:09

3 réponses

Meilleure réponse

Je pense que ce que vous dites, c'est que vous avez une séquence, dites ...

3, 9, 34, 8, 5, 25, 10

Et une opération qui permute deux des nombres, donc swap [2, 4] (zéro indexé bien sûr) donnerait

3, 9, 5, 8, 34, 25, 10

Même si l'opération n'échange pas, mais effectue plutôt une autre opération qui n'agit que sur ces deux nombres, cet algorithme fonctionnerait; en fait, cela fonctionnera pour tout ce qui change n'importe quel nombre dans ce tableau:

Tout d'abord, je garderais un tableau d'assistance de booléens qui me dirait si chaque membre de ma séquence est supérieur au nombre qui le précède, indiquant que ce nombre est en place ou en séquence par rapport à celui qui le précède. Ensuite, je garderais également un compte de combien de ces booléens sont vrais. La séquence est triée lorsque le nombre de nombres en place est égal au nombre d'éléments de la séquence. Lorsqu'une modification est apportée à n'importe quel nombre de la séquence, je vérifie avec l'algorithme suivant:

float MySequence[LengthOfSequence];
bool IsNumInPlace[LengthOfSequence];
int CountOfNumsInPlace;

... something loads MySequence ...

// this starts that helper array of booleans
IsNumInPlace[0] = true;
CountOfNumsInPlace = 1;
for (i = 1; i < LengthOfSequence; i++) {
   IsNumInPlace[i] = (MySequence[i] > MySequence[i-1]);
   if (IsNumInPlace[i]) CountOfNumsInPlace++;
}


... something changes item at index "x" in the sequence ...
// whether this number, and possibly the one after it, are in place, needs
// to be rechecked
CheckThisItem(x);
if (x < LengthOfSequence - 1) CheckThisItem(x + 1);

... the array is sorted, at this point, if CountOfNumsInPlace is equal to the number of items in the array ...

La clé est dans cette petite fonction qui augmente ou diminue le nombre "d'éléments en place", selon que la valeur à l'index donné est supérieure ou égale à la valeur de l'élément avant lui.

private void CheckThisItem(int ItemChanged) {
    bool IsNewNumInPlace= (ItemChanged == 0) ||
                          (MySequence[ItemChanged] >= MySequence[ItemChanged - 1]);
    if (IsNumInPlace[ItemChanged] && !IsNewNumInPlace) {
        CountOfNumsInPlace--;
    } else if (!IsNumInPlace[ItemChanged] && IsNewNumInPlace) {
        CountOfNumsInPlace++;
    }
    IsNumInPlace[ItemChanged] = IsNewNumInPlace;
}

Cela devrait vous donner un algorithme qui fonctionne en O (n). Vous ne comparez pas tous les éléments du tableau avec ceux qui l'entourent pour voir si le tableau est en séquence, même ceux qui n'ont pas été affectés. Vous êtes seulement à comparer l'élément modifié avec celui qui le précède et celui qui le suit.

Notez que le premier élément du tableau est considéré comme "en place" par rapport à l'élément qui le précède. Puisqu'il n'y a pas d'article devant lui (c'est le premier), il n'y a rien à dire qu'il n'est pas à sa place, donc c'est "ok" en ce qui concerne le tri.

Si votre opération modifie deux des éléments de la séquence, faites simplement la dernière partie deux fois, une fois pour chaque numéro modifié.

1
28 nov. 2017 à 15:15

Voici un excellent aide-mémoire pour plusieurs types d'algorithmes de tri; une Tri de comptage semble faire l'affaire pour vous (c'est O (n + k)) :

  1. déterminer une 'clé' entière pour chaque objet de votre liste
  2. exécuter le tri de comptage
  3. il s'exécute une fois, puis tout est trié, vous savez donc quand tout est trié.

Voici le pseudocode de Wikipédia, juste au cas où les liens se rompraient.

# variables:
#    input -- the array of items to be sorted; 
#    key(x) -- function that returns the key for item x
#    k -- a number such that all keys are in the range 0..k-1
#    count -- an array of numbers, with indexes 0..k-1, initially all zero
#    output -- an array of items, with indexes 0..n-1
#    x -- an individual input item, used within the algorithm
#    total, oldCount, i -- numbers used within the algorithm
#    Big O:  O(n + k)

# calculate the histogram of key frequencies:
for x in input:
    count[key(x)] += 1

# calculate the starting index for each key:
total = 0
for i in range(k):   # i = 0, 1, ... k-1
    oldCount = count[i]
    count[i] = total
    total += oldCount

# copy to output array, preserving order of inputs with equal keys:
for x in input:
    output[count[key(x)]] = x
    count[key(x)] += 1

return output
1
bwall 27 nov. 2017 à 18:34

Gardez une trace de la somme des valeurs absolues des différences entre les éléments adjacents. Lorsque cette somme est minimisée, ce qui se produit lorsqu'elle est égale à la valeur maximale moins la valeur minimale, alors la liste est triée.

Cela nécessite une passe pour calculer les valeurs min et max, et également pour résumer les valeurs absolues des différences.

Chaque fois que vous échangez deux éléments, soustrayez de la somme les valeurs absolues des différences de chacun d'entre eux de leurs voisins avant l'échange, puis ajoutez-les ensuite à leurs positions échangées. Puis comparez la nouvelle somme avec max - min, quand elle est égale puis arrêtez. C'est le temps O (n) et l'espace O (1).

1
samgak 28 nov. 2017 à 01:03
47517239