Trouver le minimum dans un tableau non trié en temps logarithmique

Est là une approche algorithmique pour trouver le minimum d'un tableau non-trié en temps logarithmique ( O(logn) )? Ou est-ce seulement possible dans le temps linéaire? Je ne veux pas en parallèle.

Grâce

Michael

OriginalL'auteur Michael Eilers Smith | 2011-03-24

  1. 12

    Si la liste n'est pas triée, votre recherche doit être au moins linéaire. Vous devez regarder chaque élément au moins une fois, parce que tout ce que vous n'avez pas cherché à pourrait être moins que ce que vous avez déjà vu.

    OriginalL'auteur Collin

  2. 2

    C'est pas peut-être dans le temps linéaire, parce que dans le lg n étapes vous ne pouvez inspecter lg n éléments, et parce qu'ils ne sont pas triés, les valeurs comportent pas d'informations sur d'autres valeurs dans le tableau.

    Mais il est possible dans le temps linéaire!

    OriginalL'auteur Fred Foo

  3. 2

    Va parallèle ne serait pas de l'aide en général. Si vous avez plus de processeurs que n, et on ne compte pas le temps qu'il faut pour charger les données, qui est O(n), alors oui, vous pouvez le faire en temps logarithmique. Mais supposons que vous avez, disons, 10 numéros par processeur. Il faut un certain laps de temps. Il est maintenant 20 numéros par processeur. Chaque processeur va prendre deux fois plus longtemps à croquer de ses numéros, avant de comparer les résultats en parallèle. O(n) + O(log n) = O(n).

    OriginalL'auteur Tom Zych

  4. 0

    Vous dire la valeur minimale?

    Qui est linéaire - vous parcourir votre tableau, enregistrer la position (ou de la valeur elle-même) de la moins connue de l'élément et de comparer chaque élément. Il est l'élément le plus faible sauf qu'au lieu. À la fin, vous avez la position (ou la valeur) de la moindre élément.

    J'ai fait un petit exemple en C++0x:

    #include <iostream>
#include <vector>
#include <algorithm>

int main()
{
   std::vector<int> array({5, 3, 2, 7, 5, 1, 9});

   int min = array[0];

   std::for_each(array.cbegin(), array.cend(), [&min] (const int cur) {
      min = std::min(cur, min);
   });

   std::cout << min;
}

    Vous pouvez l'exécuter à Ideone

    OriginalL'auteur MacGucky

  5. 0

    Linéairement pas, mais il peut être plus rapide que linéaire pour les moins de 10 éléments si vous utilisez une sorte de modification de quicksort. Je doute que vous êtes à la recherche pour moins de 10 points dans le tableau 🙂

    L'autre façon d'y parvenir est de demeurer dans le monde du jeu d'instructions SSE.

    Un OPCODE qui pourrait aider est CMPLEPS qui compare en parallèle 4 scalaires à un moment.

    Si vous n'êtes pas prêt à le faire dans le code parallèle cependant, je doute sérieusement que vous souhaitez utiliser ESS instructions de montage.

    OriginalL'auteur Marino Šimić

  6. 0

    Vous pouvez aussi diviser et conquérir algorithme récursif pour cela, code:

    private static Integer array[];

private static Integer findMinimum(int startIndex, int endIndex){

   //base case
   if(startIndex + 1 == endIndex || startIndex == endIndex){
     return array[startIndex] < array[endIndex] ? array[startIndex] : array[endIndex];
   }

   //recursive case
   int a = findMinimum(startIndex, (startIndex + endIndex) /2 );   
   int b = findMinimum( (startIndex + endIndex) /2 + 1, endIndex); 

   return Math.min(a, b);
}

    Cet algorithme a une durée de: O(n)

    Toutefois, si vous avez N processeur(je sais que ce n'est pas "valide" monde réel scénario, ce n'est intéressant que pour la théorie des discussions). Vous pouvez avoir des calculs parallèles et ont un temps de course: O(log n)

    Donc, si vous voulez faire quelques calculs en parallèle, vous pourriez vouloir essayer cette approche.

    OriginalL'auteur Cacho Santa