analyse recherche séquentielle

Question

Je algorithmes en train de lire en C++ par Robert Sedwick il a été mentionné comme suit

recherche séquentielle dans une table ordonnée examine le nombre N pour chaque recherche dans le pire des cas et sur les chiffres N/2 pour chaque recherche sur moyenne. Ce résultat résulte de l'hypothèse que la recherche est également susceptible de se terminer à l'un des intervalles N + 1 définis par les N nombres de la table qui mène immédiatement à l'expression (1 + 2 + 3 + 4 + ... + N + N)/N = (N + 3)/2.

Quelqu'un peut-il m'aider s'il vous plaît à comprendre comment nous sommes arrivés à l'expression ci-dessus, c'est-à-dire, comment N + 3/2 est arrivé?

Answer 1

Somme des premiers nombres entiers n (1 + 2 + 3 + ... + N) = (N + 1) N/2

Une méthode simple pour voir ceci est écrit sur la somme avant et en arrière :

1 + 2 + 3 + ... + (N-2) + (N-1) + N

N + (N-1) + (N-2) + ... + 3 + 2 + 1

puis somme des termes correspondant:

(N + 1) + (n + 1) + (n + 1) + ... + (N + 1) = N (N + 1)

division par 2 pour obtenir résultat (N + 1) N/2

Ensuite, (1 + 2 + 3 + ... + N + N)/N = ((N + 1) N/2 + N)/N = (N + 3)/2

Side note: Il y a une histoire sur le célèbre génie mathématicien Karl Friedrich Gauss (1777-1855), lorsque il était un garçon. Son maître d'école a donné à la classe le problème d'additionner les nombres de 1 à 100, pensant qu'il les occuperait pendant un certain temps. Mais Gauss a trouvé la somme 5050 après seulement quelques minutes, en utilisant le raisonnement ci-dessus. Note: Gauss était un vrai génie mais une grande partie de l'histoire de Gauss a été écrite par Gauss!

Answer 2

1 + 2 + ... + N + N = N(N+1)/2 + N = N((N+1)/2+1) = N(N + 3)/2