0 к Л6 большинство.pptx

большинство, если более половины его элементов имеют равные значения.
Например:
1,

2, 1, 2, 1, 2, 1 ;
n = 7, N(1) = 4
2) 7, 2, 7, 9, 7, 7, 7, 8, 5, 7, 1, 7, 7, 6, 7, 7, 4, 4, 7, 3 ;
n = 20, N(7) = 11
Разрешена операция сравнения: = или ≠
Требуется: в массиве, содержащем большинство, найти хотя бы одно i (1<=i<=n), такое, что xi∈большинству значений массива x. [Представитель большинства - xi]
Нахождение элемента большинства = Finding the Majority Element

03.04.2015

Теория вычислительной сложности Лекция 5

большинства ттогда, когда a появляется более ⎣n / 2⎦ раз

в массиве X, то есть, по крайней мере
⎡n/2⎤ если n нечётное
⎣n/2⎦ + 1 =
⎡n/2⎤ + 1 если n чётное


Примечания: элемент большинства является элементом с наибольшей частотой, но обратное не верно.

03.04.2015

Теория вычислительной сложности Лекция 5

встретится элемент, образующий большинство. Сложность O(n2).
Сортировать массив, а затем

сосчитать подряд стоящие равные элементы. Это занимает O(n log n). { ! Здесь используются сравнения}.
Найти медиану (⎡n/2⎤-наименьший элемент), которая (-ый) является элементом большинства (если оно есть). Это займет в худшем случае O(n), но с большим постоянным множителем, или в среднем O(n). { ! Здесь используются сравнения}.
?

03.04.2015

Теория вычислительной сложности Лекция 5

ли xi условию большинства.

do
j = random(n); // Выбор 1

= x[j];
k = 0;
for (i = 1; i<=n; i++ )
if(x[i]==c) k++;
while (k <= n/2);

Утверждаем, что сложность по числу сравнений < 2n.

03.04.2015

Теория вычислительной сложности Лекция 5

множество кортежей (i1, i2, …, ip-1, ip), p>=1 и iq∈1..n,

И при этом x[i1], x[i2], …, x[ip-1] – ∉большинству,
а x[ip] ∈большинству.
Вероятности сценариев:
Два события:
Первая попытка найти нужный индекс j – удачная,
Первая попытка найти нужный индекс j – Неудачная.
Пусть P=N/n, где N –число элементов большинства при входе n.
По условию P > ½.

03.04.2015

Теория вычислительной сложности Лекция 5

+ n),
где
P - вероятность удачной попытки; при этом количество

действий = n,
(1-P) - вероятность НЕудачной попытки; при этом количество действий = (t + n), т.е. от цикла for - количество действий = n и затем средние затраты t следующих попыток.
След.
t = n/P; и (P > ½) ⇒ t < 2n;

03.04.2015

Теория вычислительной сложности Лекция 5

на нерандомизированный (детерминированный)

Выбор кандидата
Проверка – является ли кандидат элементом

большинства

03.04.2015

Теория вычислительной сложности Лекция 5

X, то большинство старого массива остается большинством и нового. Потому

что самое худшее заключается в удалении одного элемента большинства (вместе с элементом меньшинства).
При этом размер большинства ⎣n/2⎦ +1 -1 > ⎣(n-2)/2⎦ .
Если большинство существует, то как минимум в двух позициях подряд находятся элементы большинства или X[n] является элементом большинства.

M D M D M D M D M D M D M D M D M D M D
M D M D M D M D M D M D M D M D M D M D M
M D M D M D M D M D M D M D M D M M D M D

03.04.2015

Теория вычислительной сложности Лекция 5

«нет».
-------------------------------------------------------------------
c = candidate(1); // находим лишь кандидата
int count =

0;
for (j = 1; j < n; j++)
if (x[j]==c) count++;
if (count > ⎣n/2⎦ ) return c;
else return “нет”;

03.04.2015

Теория вычислительной сложности Лекция 5

(j0)) {
j ++;
if (x[j]==c) count++;
else count--;
}
if (j==n) return

c;
else return candidate(j+1);
}

03.04.2015

Теория вычислительной сложности Лекция 5

(j = 2; j

= 1; c = x[j];}
else if (x[j] == c) count++;
else count--;
}
return c;
}

03.04.2015

Теория вычислительной сложности Лекция 5

for (j = 1; j

{count = 1; c = x[j];}
else if (x[j] == c) count++;
else count--;
}
return c;
}

03.04.2015

Теория вычислительной сложности Лекция 5

= 0;
int Count = 0;
while (i < n){
if (

Count == 0 ) {
Candidate = X[i];
Count = 1;
}
else if ( Candidate == X[i] ) Count++;
else Count--;
i++;
}
return Candidate;
}

03.04.2015

Теория вычислительной сложности Лекция 5

Не рекурсивная функция Candid3

123456777
Count > 0 , но большинства нет!
3. x[1..9] =

123455555
12
34
5
55555 ⇒ с=5 count=5 > ⎣9/2⎦ = 4 (!)

03.04.2015

Теория вычислительной сложности Лекция 5

{count=2}
555551234 {count=1} !!!
x[1..9] = 515253545

51 {count=0}
52 {count=0}
… {count=0}
5 {count=1, j=9, c=5}

03.04.2015

Теория вычислительной сложности Лекция 5

Лекция 5