Мажорирующий элемент — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство)
(Доказательство)
Строка 30: Строка 30:
  
 
Пусть данный инвариант выполняется на ''k-ом'' шаге. Тогда на ''(k+1)-ом'' шаге возможны 3 варианта:
 
Пусть данный инвариант выполняется на ''k-ом'' шаге. Тогда на ''(k+1)-ом'' шаге возможны 3 варианта:
# <tex>count == 0</tex>. Очевидно, что на подмассиве <tex>a[0..k]</tex> мажорирующего элемента не существует, так как все элементы разбились на пары. Тогда только <tex>a[k+1]</tex> может быть мажорирующим элементом.
+
# <tex>count == 0</tex><p>Очевидно, что на подмассиве <tex>a[0..k]</tex> мажорирующего элемента не существует, так как все элементы разбились на пары. Тогда только <tex>a[k+1]</tex> может быть мажорирующим элементом.</p>
 
+
# <tex>count > 0</tex> и <tex>a[k+1] == candidate</tex><p>Если на подмассиве <tex>a[0..k]</tex> существует мажорирующий элемент, то он находится в <tex>candidate</tex>. Тогда, в силу равенства <tex>a[k+1]</tex> и <tex>candidate</tex>, если на подмассиве <tex>a[0..(k+1)]</tex> существует мажорирующий элемент, то он будет равен <tex>candidate</tex>.</p>
# <tex>count > 0</tex> и <tex>a[k+1] == candidate</tex>. Если на подмассиве <tex>a[0..k]</tex> существует мажорирующий элемент, то он находится в <tex>candidate</tex>. Тогда, в силу равенства <tex>a[k+1]</tex> и <tex>candidate</tex>, если на подмассиве <tex>a[0..(k+1)]</tex> существует мажорирующий элемент, то он будет равен  
+
# <tex>count > 0</tex> и <tex>a[k+1] != candidate</tex><p>Если на подмассиве <tex>a[0..k]</tex> существует мажорирующий элемент, то он находится в <tex>candidate</tex>. Тогда, так как <tex>a[k+1]</tex> и <tex>candidate</tex> не равны, то мы нашли новую пару. Если <tex>count</tex> не станет равным нулю, то опять же мажорирующим элементом может быть только candidate, так как для всех остальных мы нашли пару, а значит они встречаются не более <tex>N/2</tex> раз.</p>
 
 
# <tex>count > 0</tex> и <tex>a[k+1] != candidate</tex>. Если на подмассиве <tex>a[0..k]</tex> существует мажорирующий элемент, то он находится в <tex>candidate</tex>.
 
  
 
== Обобщение на случай поиска элемента, встречающегося N/K раз ==
 
== Обобщение на случай поиска элемента, встречающегося N/K раз ==

Версия 17:22, 24 мая 2013

Формулировка задачи

Требуется в массиве длиной N найти элемент, встречающийся более N/2 раз. Гарантируется, что такой элемент существует.

Решение за O(n)

Алгоритм можно представить следующим образом: пусть на вечеринке собрались [math]N[/math] людей, и каждому из них соответствует один элемент из массива. Когда встречаются двое с разными элементами, то они садятся. В конце концов останутся стоять только гости с одинаковыми элементами. Это и есть искомый элемент.

Псевдокод

 findMajorityElement(a, N)
   count = 0 // количество людей, оставшихся стоять
   candidate = null
   
   for i = 0 to N - 1
     if count == 0 // никто не стоит
       candidate = a[i] // встанет текущий элемент
       count++ // увеличим количество стоящих
     else // кто-то стоит
       if a[i] == candidate // стоит такой же элемент
         count++ // увеличим количество стоящих
       else // стоит другой элемент => подобрали пару
         count-- // уменьшим количество стоящих
    
    return candidate

Доказательство

На i-ом шаге выполняется следующий инвариант: если [math]count \gt 0[/math], то [math]candidate[/math] - мажорирующий элемент на подмассиве [math]a[0..i][/math], либо мажорирующего элемента на данном подмассиве не существует. Тогда на N-ом шаге [math]candidate[/math] будет содержать мажорирующий элемент на всем массиве, т.к. гарантируется его существование. Покажем, что данный инвариант всегда выполняется.

Пусть данный инвариант выполняется на k-ом шаге. Тогда на (k+1)-ом шаге возможны 3 варианта:

  1. [math]count == 0[/math]

    Очевидно, что на подмассиве [math]a[0..k][/math] мажорирующего элемента не существует, так как все элементы разбились на пары. Тогда только [math]a[k+1][/math] может быть мажорирующим элементом.

  2. [math]count \gt 0[/math] и [math]a[k+1] == candidate[/math]

    Если на подмассиве [math]a[0..k][/math] существует мажорирующий элемент, то он находится в [math]candidate[/math]. Тогда, в силу равенства [math]a[k+1][/math] и [math]candidate[/math], если на подмассиве [math]a[0..(k+1)][/math] существует мажорирующий элемент, то он будет равен [math]candidate[/math].

  3. [math]count \gt 0[/math] и [math]a[k+1] != candidate[/math]

    Если на подмассиве [math]a[0..k][/math] существует мажорирующий элемент, то он находится в [math]candidate[/math]. Тогда, так как [math]a[k+1][/math] и [math]candidate[/math] не равны, то мы нашли новую пару. Если [math]count[/math] не станет равным нулю, то опять же мажорирующим элементом может быть только candidate, так как для всех остальных мы нашли пару, а значит они встречаются не более [math]N/2[/math] раз.

Обобщение на случай поиска элемента, встречающегося N/K раз

"Хитрое" решение

Выберем случайный элемент в массиве и проверим, встречается ли он больше, чем [math]N / K[/math] раз. Будем делать так, пока не найдем подходящий элемент. Утверждается, что данный алгоритм в среднем работает за [math]O(N \cdot K)[/math]

Псевдокод

findMajorityElement(a, N, K)
  while true
    candidate = a[random(N)]
    count = 0
    for i = 0 to N - 1
      if a[i] == candidate
        count++
    if count > N / K
      return candidate

Доказательство

На каждом шаге мы берем случайный элемент. Проверка на мажорируемость выполняется за [math]O(N)[/math]. Вероятность, что мы выбрали элемент "удачно" составляет [math]1 / K[/math]. Тогда, в среднем, мы будем делать [math]K[/math] проверок. Итоговая сложность [math]O(N \cdot K)[/math].

Источники