Expected Highs

Question

I have an algorithm that takes an array as an argument and returns its maximum value.

find_max(as) :=
    max = as[0]
    for i = 1 ... len(as) {
        if max < as[i] then max = as[i]
   }
    return max

My question is, given that the array is initially in a (uniformly) random permutation and that all its elements are different, what is the expected number of times the variable is maxupdated (ignoring the original assignment).

For example, if as = [1, 3, 2], then the number of updates for maxwill be equal to 1 (when reading a value of 3).

Answer 1

Empirical decision

Modeling of various sizes of arrays with several tests can be performed and analyzed:

#include <iostream>
#include <fstream>
#include <cstdlib>
#define UPTO 10000
#define TRIALS 100

using namespace std;

int arr[UPTO];

int main(void){
  ofstream outfile ("tabsep.txt");
  for(int i = 1; i < UPTO; i++){
    int sum = 0;
    for(int iter = 0; iter < TRIALS; iter++){
      for(int j = 0; j < i; j++){
        arr[j] = rand();
      }
      int max = arr[0];
      int times_changed = 0;
      for(int j = 0; j < i; j++){
        if (arr[j] > max){
          max = arr[j];
          times_changed++;
        }
      }
      sum += times_changed;
    }
    int avg = sum/TRIALS;
    outfile << i << "\t" << avg << "\n";
    cout << "\r" << i;
  }
  outfile.close();
  cout << endl;
  return 0;
}

---

, :

---

, O (log n).

---

:

• , 0... n
• m
• m + 1... n, (m + n)/2
• , , , 2
• , , O (log n)

Answer 2

, 1, 2,..., N.

X_i, = 1..N - , 1, - .

, , : M = X_1 + X_2 +... + X_N.

( ) E (M) = E (X_1 + X_2 +... + X_N). , E (X_1) + E (X_2) +.. + E (X_N), prob (1 max) + prob (2 max) +... + prob (N ) ( X_i 0 1).

? i, + 1, + 2,..., N. 1/(N-i + 1) ( ).

... prob (i max) = 1/(N-i + 1), 1/N + 1/(N-1) +.. + 1/3 + 1/2 + 1/1

(N), ln (N) + emc, emc ~ = 0,5772156649, -.

, (N) - 1 ln (N) - 0.4227843351.

:

• N = 1, . (1) - 1 = 0.
• N = 2, - [1, 2] [2, 1]. , , 1/2. (2) - 1 = 1/2.
• N = 3, - [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [ 3, 2, 1]. - 2, 1, 1, 1, 0, 0 . (2 + 1 + 1 + 1)/6 = 5/6. (3) - 1 = 1/2 + 1/3 = 5/6.

, !

Answer 3

( ) - O (n). , .

, , - , ? 1 n-1.