Simple “valeur maximale dans la gamme” et de la complexité des calculs

Je suis assez nouveau à ce genre de choses et j'ai besoin de votre aide.

Je dois construire un algorithme simple et efficace qui retourne la valeur maximale d'un tableau avec la taille de n qui contient les nombres 1,2,...n avec les répétitions.

Puis-je déterminer le meilleur temps de course, la moyenne des temps d'exécution et le pire temps d'exécution.

J'ai donc deux questions:

  1. Tout d'abord, je suis en train d'essayer de comprendre ce qu'est l'idée d'exiger une solution efficace pour cet algorithme simple. Autant je comprends que je ne dois avoir une simple boucle de 1 à n et de regarder pour la valeur maximale. Est "efficace" de l'algorithme de points que Si j'ai trouver la valeur de n dans le tableau, j'pouvez arrêter de chercher plus, parce que c'est la valeur maximale dans le tableau?
  2. Comment puis-je déterminer le meilleur temps de course et la moyenne des temps d'exécution à l'aide de l'effet, alors que le calcul de la moyenne des temps d'exécution, qu'Il est d'une distribution uniforme.
    C'est, chaque cellule de la matrice a une chance de 1/n à la valeur maximale.

Merci beaucoup d'avance!

Les sons comme des devoirs... qu'avez-vous venir jusqu'ici? Astuce: triés matrices O(1) environnement d'exécution pour les valeurs max/min.
Mais la détermination du tableau est trié est O(n) 😐
c'est donc tout simplement en tirant sur les valeurs max/min sur n'importe quel tableau.
le tableau n'est pas trié. Je ne suis pas exigeant une solution, mais quelques explications pour réponse concrète. Comme pour ce que je suis venu jusqu'ici, je l'ai écrit dans ma question.
"La valeur maximale dans un tableau avec la taille de n qui contient les nombres 1,2,...n avec les répétitions" est évidemment n, n'est-ce pas?

OriginalL'auteur SyndicatorBBB | 2012-10-31

  1. 7

    Meilleur des cas - trouver le max de l'élément de la première (O(1)), dans le pire des cas - c'est le dernier élément vérifié (O(n)).

    La partie la plus délicate est la moyenne des cas.

    À trouver le moyen de cas nous avons besoin de la attendu nombre d'itérations!

    Puisque vous pouvez vous arrêter une fois que vous trouvez le maximum, nous pouvons diviser le problème en deux parties:

    1. [0,n-1): Depuis en moyenne (en supposant que l'uniforme de la distribution indépendante pour chaque élément) - le nombre n a une probabilité 1/n d'être en chaque lieu, alors le nombre d'itérations de cette pièce est 1/n + 2*((n-1)/n)/n + 3 * ((n-1)/n)^2/n + ... + (n-1) * ((n-1)/n)^(n-2)/n 1

      La formule ci-dessus donne un laide de la formule qui est O(n)
    2. Le dernier élément va être vérifié si le premier n-1 éléments ne contiennent pas la valeur n: vous devez ajouter au-dessus n* ((n-1)/n)^(n-1), qui est O(n) (lim à l'infini est 1/e * n).

    Ce totaux dans O(n) moyenne de temps de la solution.

    (1): La formule de chaque élément est j*((n-1)/n)^(j-1) * (1/n) parce que:

    • j - le nombre d'éléments vérifiés (nombre d'itérations)
    • ((n-1)/n)^(j-1) - Probabilité qu'il n'y a pas de n dans les éléments précédents
    • (1/n) - Probabilité que ce nombre est n.
    Wow @amit je n'ai pas de mots. Si bien mis. Vraiment conscient de ce fait.
    "Avec les doublons" peu dit que ce n'est pas une permutation aléatoire. Simplement n entiers aléatoires dans la gamme 1..n.
    Le terme de permutation a eu tort, mais notez que la caclulation n'a pas assumé de permutation, il suppose une distribution uniforme pour chaque élément de sorte qu'il (chaque élément) a 1/n chance d'être le max, et (n-1)/n de ne pas être. Je vais corriger la terminologie. Je vous remercie pour votre commentaire.
    Pourquoi est-ce le meilleur des cas O(1)? Vous ne pouvez pas être certain que tout un élément d'un tableau est le max sans savoir ce qui est dans le reste de la matrice...
    Notez que la question des états que le tableau contains the numbers 1,2,...n with repetitions. Le meilleur des cas est en fait: lire le premier élément, le voir, c'est n, et de le retourner. Ce est O(1).

    OriginalL'auteur amit

  2. 2

    L'algorithme fonctionne comme cela, vous sélectionnez d'abord un certain nombre (dans ce cas, je sélectionne le premier numéro de la matrice, et prétendre que c'est le max, puis je la compare à la prochaine nombre et si il est plus grand je prends ça comme le nouveau max, jusqu'à ce que j'ai fini de chercher dans le tableau), le code est en C:

    #include <stdio.h>
#define SIZE 100

typedef struct{
    int val;
    int loc;
} find;

/* Functions declaration (Prototype) */
find maxFinder( int * const a );

int main( void )
{
    int response[ SIZE ]=
       { 1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100,
         1, 3, 5, 7,  8, 9, 0, 10, 65, 100 };

    printf( "The max number is %d located in the index %d.\n", maxFinder( response ).val, maxFinder( response ).loc );
    return 0;
}

 find maxFinder( int * const a )
 {
    /* Local Variables initialization & declaration */
    int i;
    find result;

    result.loc = 0;
    result.val = *( a + 0 );

    for( i = 1; i < SIZE; i++ ){
        if ( result.val < *( a + i ) ){
            result.loc = i;
            result.val = *( a + i );
        }
    }
    return result;
 }
    Ne devriez-vous pas utiliser le fait que les nombres sont compris entre 1... TAILLE?
    La TAILLE est une valeur constante que vous devez déclarer, dans mon cas, c'est 100.
    Dans ce cas, SIZE = n, et vos valeurs sont comprises entre 1...n. Ce n'est pas un cas général, comme vous l'avez montré.
    C'est le cas général, il suffit de changer la TAILLE de la valeur que vous souhaitez, et d'un morceau de 0 (le premier élément du tableau jusqu'à ce que le tableau des finitions (n-1)
    Merci @Alberto

    OriginalL'auteur Alberto Bonsanto

  3. 2

    Si il n'y a pas d'information préalable sur le tableau (par exemple il est triée), il n'est pas le cas le pire ou le meilleur des cas, et que Vous avez à analyser tous les éléments pour trouver le Max, et il faut O(n) fois.

    Aussi, de connaître la distribution de la probabilité d'obtenir la valeur maximum de chaque cellule est inutile en général (à moins qu'il réduit votre espace de recherche. par exemple, Si vous savez que seulement un nombre constant de cellules ont une probabilité non nulle d'obtenir la valeur max, alors vous avez juste besoin de recherche de ces cellules et cela prend du temps constant). Ainsi, en général

    Meilleur des cas, les temps d'exécution = Pires temps d'exécution = moyenne des temps d'exécution = O(n)

    OriginalL'auteur nmoses

  4. 1

    Le pire et le meilleur des cas simples. La moyenne des cas est le plus intéressant. Regardez la page de Wikipedia pour La Répartition Géométrique.

    Dans le meilleur des cas - dans le cas où c'est le premier élément : O(1) et le pire cas : O(n) , est ce que le droit?
    En fonction de vos commentaires, vous semblez comme vous êtes confiant et que vous comprenez l'idée. Aller avec votre instinct 🙂
    Merci @japreiss

    OriginalL'auteur japreiss