Вчера научился искать минимальный элемент массива
Попутно придумал забавную задачку, которую решил не сразу.
Хотя формулировочка проста до неприличия.

//Ищем минимальный элемент в случайном массиве
for(int i=0,m=MAX_INT;i<N;i++)
  if(a[i]<m)
    m=a[i];//Cколько раз (в среднем) выполнится это строчка?

PS
Всегда найдутся товарищи, достаточно дотошные,
чтобы желать точной постановки,
и в то же время достаточно ленивые,
чтобы напрячься и сделать её самому.
Для таких объясняю, что значит "в среднем".

- Заполните массив случайным образом. 
(Генератор даже не обязательно равномерный. 
Достаточно, чтобы он был "хорошим", 
т.е. давал слабую корелляцию между соседями.
И ещё он должен быть сильно "шире" чем N, 
чтобы в массиве было поменьше одинаковых чисел)

- Подсчитайте число присваиваний при нахождении минимального элемента. 
Это число будет зависеть как от числа элементов, 
так и от самой случайной реализации массива.

- Проделайте всё это много-много раз и возьмите среднее от всех ответов. 
Результат будет функцией только от длины массива F(N). 
Вид этой функции я и прошу найти "ручками".

Здравствуйте, Pushkin, Вы писали:

...

P>

P>//Ищем минимальный элемент в случайном массиве
P>for(int i=0,m=MAX_INT;i<N;i++)
P>  if(a[i]<m)
P>    m=a[i];//Cколько раз (в среднем) выполнится это строчка?
P>

P>PS
P>Всегда найдутся товарищи, достаточно дотошные,
P>чтобы желать точной постановки,
P>и в то же время достаточно ленивые,
P>чтобы напрячься и сделать её самому.

и даже достаточно ленивые, чтобы её решать.

Поэтому, в отместку, другая задачка: как при поиске
минимального элемента не делать присваиваний

  m=a[i];

вообще ?

Здравствуйте, mrhru, Вы писали:

M> и даже достаточно ленивые, чтобы её решать.

ай-ай-ай

M>Поэтому, в отместку, другая задачка: как при поиске
M>минимального элемента не делать присваиваний
M>

M>  m=a[i];
M>

M>вообще ?

for(int i=0;i<N-1;i++)
  if(a[i]<a[i+1])
    a[i+1]^=a[i]^=a[i+1]^=a[i];
return a[N-1];

Здравствуйте, Pushkin, Вы писали:

P>

P>//Ищем минимальный элемент в случайном массиве
P>for(int i=0,m=MAX_INT;i<N;i++)
P>  if(a[i]<m)
P>    m=a[i];//Cколько раз (в среднем) выполнится это строчка?
P>

P>Вид этой функции я и прошу найти "ручками".
P>[/ccode]

Найдем вероятность того, что последний элемент массива будет минимальным.
Предыдущие числа разбивают диапозон целых чисел на N отрезков. Вероятность того, что последний будет минимальным равна вероятности попадания последнего числа в первый отрезок. При достаточно равномерном распределении она равна 1/N.
Далее, по индукции, получаем гармонический ряд:
F(N) = 1 + 1/2 + 1/3 + ... + 1/N ~ C + ln(N) + 1/2N, где C = 0.5772... — постоянная Эйлера-Маскерони

Здравствуйте, Pushkin, Вы писали:
...
M>> и даже достаточно ленивые, чтобы её решать.

P>ай-ай-ай



...
P>

P>for(int i=0;i<N-1;i++)
P>  if(a[i]<a[i+1])
P>    a[i+1]^=a[i]^=a[i+1]^=a[i];
P>return a[N-1];
P>

:super:/2.

А вот без жульничества.

int a[N];

int C(int p)
{
  if( p == (N - 1) ){
    return a[p];
  }else{
    return min( a[p], C(p+1) );
  }
}
...
  m = C(0);

Здравствуйте, Pushkin, Вы писали:

P>

P>for(int i=0;i<N-1;i++)
P>  if(a[i]<a[i+1])
P>    a[i+1]^=a[i]^=a[i+1]^=a[i];
P>return a[N-1];
P>

Будьте проще, и к вам undefined behaviour не потянется.

int iGreatest = 0, iCurrent;
for(iCurrent = 1; iCurrent < N; ++i)
  if(a[iGreatest] < a[iCurrent])
    iGreatest = iCurrent;

ибо присваивание целых чисел легче (не тяжелее), чем измывательства над данными любого другого типа.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Pushkin, Вы писали:

P>>

P>>for(int i=0;i<N-1;i++)
P>>  if(a[i]<a[i+1])
P>>    a[i+1]^=a[i]^=a[i+1]^=a[i];
P>>return a[N-1];
P>>

К>Будьте проще, и к вам undefined behaviour не потянется.
К>

К>int iGreatest = 0, iCurrent;
К>for(iCurrent = 1; iCurrent < N; ++i)
К>  if(a[iGreatest] < a[iCurrent])
К>    iGreatest = iCurrent;
К>

К>ибо присваивание целых чисел легче (не тяжелее), чем измывательства над данными любого другого типа.



Спасибо! Вот я ещё на один бит поумнел.

Здравствуйте, Кодт, Вы писали:

К>Будьте проще, и к вам undefined behaviour не потянется.

Вот уж точно по Паркинсону.
Самое большое сопротивление обычно вызывает самое безобидное место.
Вы задачу, блин решайте, умные!

PS
Хотя ты, конечно, как всегда прав

Здравствуйте, MichaelP, Вы писали:

MP>Найдем вероятность того, что последний элемент массива будет минимальным.
MP>Предыдущие числа разбивают диапозон целых чисел на N отрезков. Вероятность того, что последний будет минимальным равна вероятности попадания последнего числа в первый отрезок. При достаточно равномерном распределении она равна 1/N.
MP>Далее, по индукции, получаем гармонический ряд:
MP>F(N) = 1 + 1/2 + 1/3 + ... + 1/N ~ C + ln(N) + 1/2N, где C = 0.5772... — постоянная Эйлера-Маскерони

У меня такой же ответ.
Но получил я его чуть иначе, и мне не потребовалась равномерность генератора.

Здравствуйте, Pushkin, Вы писали:

P>Попутно придумал забавную задачку, которую решил не сразу.
P>Хотя формулировочка проста до неприличия.

P>

P>//Ищем минимальный элемент в случайном массиве
P>for(int i=0,m=MAX_INT;i<N;i++)
P>  if(a[i]<m)
P>    m=a[i];//Cколько раз (в среднем) выполнится это строчка?
P>

Задачка вообще-то для математиков, немного знакомых с тервером.
f(N)=2-1/(2^(N-1))
раписывать ломает, но если кому интересно могу

Здравствуйте, Demon, Вы писали:

D>Задачка вообще-то для математиков, немного знакомых с тервером.
D>f(N)=2-1/(2^(N-1))
D>раписывать ломает, но если кому интересно могу

Ты хочешь сказать, что в длиннющем массиве
присваивание выполнится не более 2-х раз?
Имхо оптимист

Здравствуйте, MichaelP, Вы писали:

[skip]

MP>Найдем вероятность того, что последний элемент массива будет минимальным.
MP>Предыдущие числа разбивают диапозон целых чисел на N отрезков. Вероятность того, что последний будет минимальным равна вероятности попадания последнего числа в первый отрезок. При достаточно равномерном распределении она равна 1/N.

Это и так понятно. Поскольку числа случайные и не коррелируют между собой, то вероятность
того что некоторый, даже не обязательно последний, элемент массива минимальный, равна
1/N.

MP>Далее, по индукции, получаем гармонический ряд:

А вот это мне не понятно. Какие величины складываются?
Нельзя ли по-подробнее?

MP>F(N) = 1 + 1/2 + 1/3 + ... + 1/N ~ C + ln(N) + 1/2N, где C = 0.5772... — постоянная Эйлера-Маскерони

Здравствуйте, Demon, Вы писали:

D>Здравствуйте, Pushkin, Вы писали:

P>>Попутно придумал забавную задачку, которую решил не сразу.
P>>Хотя формулировочка проста до неприличия.

P>>

P>>//Ищем минимальный элемент в случайном массиве
P>>for(int i=0,m=MAX_INT;i<N;i++)
P>>  if(a[i]<m)
P>>    m=a[i];//Cколько раз (в среднем) выполнится это строчка?
P>>

D>Задачка вообще-то для математиков, немного знакомых с тервером.
D>f(N)=2-1/(2^(N-1))
D>раписывать ломает, но если кому интересно могу
Распишу т.к. найден другой ответ
Пусть 0<=a[i]<=1
m[i] — min на i-ом шаге
вероятность того что b[i+1]<m[i] равна m[i], а M(m[i+1])=m[i]/2 т.е. можно считать что m[i+1]=m[i]/2
суммируем и получаем выше указанный результат

Здравствуйте, Pushkin, Вы писали:

D>>f(N)=2-1/(2^(N-1))

P>Ты хочешь сказать, что в длиннющем массиве
P>присваивание выполнится не более 2-х раз?
Меня это тоже удивляет, но дырку в своей логике я не могу найти

Здравствуйте, Demon, Вы писали:

D>Распишу т.к. найден другой ответ
D>Пусть 0<=a[i]<=1
D>m[i] — min на i-ом шаге
D>вероятность того что b[i+1]<m[i] равна m[i],

до этого места верно

D>а M(m[i+1])=m[i]/2 т.е. можно считать что m[i+1]=m[i]/2

Если M(m[i+1]) это мат. ожидание минимума на следующем шаге, то оно равно

M(m[i+1]) = m[i] * m[i]/2 + (1-m[i]) * m[i] = m[i] — m[i]^2/2

Неясно, что ты будешь делать дальше с этим крокодилом.
Кроме того переход, обозначенный словами "т.е. можно считать" сомнителен.

Здравствуйте, Pushkin, Вы писали:

MP>>Найдем вероятность того, что последний элемент массива будет минимальным.
MP>>Предыдущие числа разбивают диапозон целых чисел на N отрезков. Вероятность того, что последний будет минимальным равна вероятности попадания последнего числа в первый отрезок. При достаточно равномерном распределении она равна 1/N.
MP>>Далее, по индукции, получаем гармонический ряд:
MP>>F(N) = 1 + 1/2 + 1/3 + ... + 1/N ~ C + ln(N) + 1/2N, где C = 0.5772... — постоянная Эйлера-Маскерони

P> У меня такой же ответ.
P>Но получил я его чуть иначе, и мне не потребовалась равномерность генератора.

Согласен. Усилим утверждение:
Если числа распределены одинаково и независимо, то вероятности того, что i-ое из N чисел минимально, равны. Следовательно, вероятность того, что последнее минимально равно 1/N. Далее по тексту.

Здравствуйте, Sergeem, Вы писали:

S>А вот это мне не понятно. Какие величины складываются?
S>Нельзя ли по-подробнее?

Теперь уже я переведу MichelP для широкой публики.

Найдём рекуррентную формулу для F(N).
Т.е. пусть мы знаем F(N-1) и хотим получить F(N).

Если в случайной реализации массива a[N]
минимальный элемент не на последнем месте,
то можно считать, что это массив из N-1 элемента,
так как последний элемент точно не добавит приравнивания.

Если числа распределены одинаково и независимо,
то вероятности того, что i-ое из N чисел минимально
не зависит от i и равна 1/N. В том числе и для i=N-1.

Т.е. только в 1/N реализациях от общего числа больший массив
что-то добавляет к искомому числу по сравнению с меньшим.

Поэтому F(N) = F(N-1) + 1/N = 1 + 1/2 + .... + 1/N

Моё решение было несколько другим.

Пусть у нас всего 2 элемента.
Тогда минимальный из них точно влезет в ячейку.
А вот другой влезет только если будет стоять раньше минимального.
Вероятность стоять раньше из двух 1/2.
Поэтому среднее число присваиваний 1+1/2 = 3/2

Теперь 3 элемента.
Минимальный так и так влезет — уже имеем F=1+
Второй по величине влезет если окажется раньше минимального F=1+1/2+
Третий влезет, если окажется первым из трёх (себя и двух минимальных) F=1+1/2+1/3

Ясно, что и дальше ничего не мешает продолжать в том же духе.

Здравствуйте, Pushkin, Вы писали:


P>Если числа распределены одинаково и независимо,
P>то вероятности того, что i-ое из N чисел минимально
P>не зависит от i и равна 1/N. В том числе и для i=N-1.

Ради справедливости замечу, что это рассуждение, как я только что заметил, раньше меня привел Sergeem

Автор: Sergeem
Дата: 05.03.03

.

Здравствуйте, Pushkin, Вы писали:

P>Моё решение было несколько другим.

Господи, да совсем же всё просто, только сейчас в голову пришло

Первый элемент кладётся в ячейку с вероятностью 1.
Второй элемент с вероятнстью 1/2 — если он окажется меньше первого.
Третий элемент с вероятностью 1/3 — если он меньше первого и второго.
n-ый элемент кладётся с вероятностью 1/n — если он наименьший из первых n
(а любой из них имет равные права быть наименьшим)

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, Pushkin, Вы писали:

P>>Моё решение было несколько другим.

P>Господи, да совсем же всё просто, только сейчас в голову пришло

P>Первый элемент кладётся в ячейку с вероятностью 1.
P>Второй элемент с вероятнстью 1/2 — если он окажется меньше первого.
P>Третий элемент с вероятностью 1/3 — если он меньше первого и второго.
P>n-ый элемент кладётся с вероятностью 1/n — если он наименьший из первых n
P>(а любой из них имет равные права быть наименьшим)

Собственно это я имел ввиду в своем доказательстве.

Здравствуйте, MichaelP, Вы писали:

MP>Собственно это я имел ввиду в своем доказательстве.

"Иметь в виду" это все могут
Словами надо говорить.
Как можно короче, яснее и неоспоримее.
Но ты всё равно молодец

Здравствуйте, Pushkin, Вы писали:

К>>Будьте проще, и к вам undefined behaviour не потянется.

P>Вот уж точно по Паркинсону.
P>Самое большое сопротивление обычно вызывает самое безобидное место.

По врачу Паркинсону?

P>Вы задачу, блин решайте, умные!

Кстати о блинах. Масленица ж!

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, mrhru, Вы писали:

P>

P>for(int i=0;i<N-1;i++)
P>  if(a[i]<a[i+1])
P>    a[i+1]^=a[i]^=a[i+1]^=a[i];
P>return a[N-1];
P>

Это сортировка пузырьком, первый проход.

Вопрос: а сколько обменов будет совершено здесь?

К>Это сортировка пузырьком, первый проход.

К>Вопрос: а сколько обменов будет совершено здесь?

И, собственно, ответ:

Пусть на отрезке [0..k] было S(k) обменов. При этом a[k] стал наибольшим.
В паре a[k], a[k+1] обмен не состоится, если a[k+1] — максимум из a[0..k+1].

Т.е. матожидание S(k+1) = S(k) + k/(k+1)

Получаем ряд:

S(N) =   0 +   1/2 +   2/3 +   3/4 + ... +   (N-1)/N =
     = 1-1 + 1-1/2 + 1-1/3 + 1-1/4 + ... + 1-    1/N =

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

Здравствуйте, Кодт, Вы писали:

К>>Это сортировка пузырьком, первый проход.
К>>Вопрос: а сколько обменов будет совершено здесь?
К>И, собственно, ответ:
К> N — (1+1/2+1/3+...+1/N)


Логическим завершением будет вопрос о количестве присваиваний
во всей пузырьковой сортировке массива из N элементов.
Но на него я пока ответить не могу

Здравствуйте, Pushkin, Вы писали:

P>Логическим завершением будет вопрос о количестве присваиваний
P>во всей пузырьковой сортировке массива из N элементов.
P>Но на него я пока ответить не могу

Могу!

Сначала немного модифицируем алгоритм пузырьковой сортировки. В классическом варианте мы должны сначала сравнить и если надо обменять первую пару.Затем вторую и так далее до конца. Затем прделать это много раз, снижая границу.

Но заметим, что обслужив вторую пару, мы вполне можем ДО того, как обслужим все оставшиеся СРАЗУ обслужить первую по второму разу. От этого ровно ничего не изменится, никакие сравнения не изменят результата. Далее надо обслуживать третью пару, никуда не деться. Но потом можно сразу вторую по второму разу и первую по третьему.

Смотрите, что получается. Впереди бежит фронт и с каждым шагом пускает назад упорядочивающую волну. В результате весь хвост всегда полностью упорядочен. Назовём это пузырьковой сортировкой в форме реверсивного упорядочивания. Ещё раз подчёркиваю, она полностью эквивалентна классическому алгоритму. Мы не изменили ни числа сравнений ни числа присваиваний — просто перестановили свои операции.

Но в этой форме всё становится совершенно прозрачным!
Раз хвост всегда упорядочен, то в процессе волны надо просто найти место головному элементу. Ясно, что ему всё равно где остановиться — данный элемент группы с одинаковой вероятностью оказывается на любом месте в упорядоченном массиве. Значит средний путь n-того элемента до своего места n/2. Теперь надо просто сложить эти числа от 1 до N — получится простой ответ

F(N) = 1/2 + 2/2 + 3/2 + ... (N-1)/2 = N*(N-1)/4

Замечательный квадратичный рост.
Такой же как у числа сравнений.
Точнее, ровно в 2 раза меньше!
Это немедленно рождает желание как-нибудь поспекулировать на тему того, что каждое второе сравнение успешно. Но, я не думаю, что тут есть очевидное объяснение. Ведь совершенно ясно, что в процессе всплывания первого пузырька мы чем дальше, тем увереннее выполняем обмен. Т.е. вероятность разных результатов сравнений вовсе не фифти-фифти. Именно поэтому для числа обменов при первом протаскивании мы получили N-lnN а вовсе не N/2. С другой стороны, протащив один раз, мы явно что-то упорядочили сзади, и при следующем проходе сравнения будут уже смещены в сторону не-обмена.

И наконец, последнее замечание.
Реверсивное упорядочивание эквивалентно классическому алгоритму. Но оно лучше! Потому что может быть улучшено. Действительно, раз там всё сзади упорядочено, то на фига продолжать сравнивать после первой неудачи? Как только нашли новому элементу место, так и бросаем это дело! Таким образом, число сравнений оказывается практически равно числу присваиваний (всего лишь на N больше), т.е. для больших N ополовинивается.

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, Pushkin, Вы писали:

P>>Логическим завершением будет вопрос о количестве присваиваний
P>>во всей пузырьковой сортировке массива из N элементов.
P>F(N) = N*(N-1)/4

Для простой сортировки всё проще (и лучше!), чем для пузырьковой.

for(int n=N;n>1;n++)
{
  int im,m=-MAX_INT;
  for(int i=0;i<n;i++)
  if(a[i]>m)
  {
    im=i;
    m=a[i];    
  }
  a[im]=a[n-1];
  a[n-1]=m;
}

Совершенно ясно, что вытащив за один проход максимальный наверх,
мы ничего особо не изменили в хвосте.
Поэтому если для одного прохода осуществлено присваиваний

S(n)=1+1/2+1/3+...+1/n

то для всех проходов их будет

S(N)+S(N-1)+...S(1) = N*S(n)+S(n)-N

Те 2N присваиваний, которые в конце внешнего цикла можно добавить,
но это не меняет дела — рост NlnN — гораздо лучше, чем у пузырьков.

Может показаться разумным не заводить специальную ячейку m,
а сразу копить максимум в последнем элементе массива.

for(int n=N-1;n>0;n++)
  for(int i=0;i<n;i++)
    if(a[i]>a[n])
      SWAP(a[i],a[n]);

Казалось бы, мы ничего не теряем по сравнению с предыдущим случаем,
более того даже слегка упорядочиваем левую часть, подтаскивая к концу большие элементы.
Всяко число обменов не должно быть больше, чем NlnN

Но запрограммив таким образом я испытал шок — квадратичный рост! (0.075*N^2)
Точно выводить ручками я поленился, но качественно в чём дело, понял. Дело в том, что подтаскивая по ходу дела большие элементы поближе к концу массива мы делаем себе не лучше, а хуже! Если бы они в начале остававались, то рано попадали бы в ячейку максимума и не пускали остальных. А так, мы вынуждены пихаться малышами в начале, а потом ещё пихаться тяжеловесами в конце. Приравниваний получается больше.

Как всё забавно, на пустом месте казалось бы

Здравствуйте, Pushkin, Вы писали:


P>

P>for(int n=N-1;n>0;n++)
P>  for(int i=0;i<n;i++)
P>    if(a[i]>a[n])
P>      SWAP(a[i],a[n]);    
P>

P>Казалось бы, мы ничего не теряем по сравнению с предыдущим случаем,
P>более того даже слегка упорядочиваем левую часть, подтаскивая к концу большие элементы.
P>Всяко число обменов не должно быть больше, чем NlnN

P>Но запрограммив таким образом я испытал шок — квадратичный рост! (0.075*N^2)
P>Точно выводить ручками я поленился, но качественно в чём дело, понял. Дело в том, что подтаскивая по ходу дела большие элементы поближе к концу массива мы делаем себе не лучше, а хуже! Если бы они в начале остававались, то рано попадали бы в ячейку максимума и не пускали остальных. А так, мы вынуждены пихаться малышами в начале, а потом ещё пихаться тяжеловесами в конце. Приравниваний получается больше.

А может так попробовать:

for(int n=N-1;n>0;n--)
  for(int i=n-1;i>=0;i--)
    if(a[i]>a[n])
      SWAP(a[i],a[n]);

К сожалению, на эксперименты времени нет

Здравствуйте, MichaelP, Вы писали:

MP>А может так попробовать:
MP>

MP>for(int n=N-1;n>0;n--)
MP>  for(int i=n-1;i>=0;i--)
MP>    if(a[i]>a[n])
MP>      SWAP(a[i],a[n]);    
MP>

Вся эта задача — сплошь обманутая интуиция.
Я в принципе ожидал, что не улучшится, суть-то не изменилась — всё равно мы оттаскиваем нужные числа подальше, а потом подольше до них мудохаемся. Но чтобы время ухудшилось, этого даже я не предполагал. Нет, зависимость осталась квадратичной, но коэффициент перед N^2 увеличился с 0.8 до 2.4