Блог

Анализ среднего случая довольно сложно выполнить для непересекающейся структуры данных. Наименьшая из проблем заключается в том, что ответ зависит от того, как определить среднее значение (относительно операции объединения). Например, в приведенном ниже лесу. Для описания каждое дерево представлено множеством.

{0}, {1}, {2}, {3}, {4, 5, 6,8 }

мы могли бы сказать, что, поскольку существует пять деревьев, существует 5 * 4 = 20 одинаково вероятных результатов следующего объединения (поскольку могут быть объединены любые два разных дерева). Конечно, следствием этой модели является то, что вероятность того, что следующее объединение будет включать большое дерево, составляет всего 2/5.

Другая модель может сказать, что все объединения между любыми двумя элементами в разных деревьях одинаково вероятны, поэтому большее дерево с большей вероятностью будет вовлечено в следующее объединение, чем меньшее дерево. В приведенном выше примере существует вероятность 8/11, что большое дерево будет вовлечено в следующее объединение, поскольку (игнорируя симметрии) существует 6 способов объединения двух элементов в {1, 2, 3, 4}, и 16 способов объединить элемент в {5, 6,7, 8} с элементом в {1, 2, 3, 4}. Существует еще больше моделей, и нет общего согласия по поводу того, какая из них является лучшей. Среднее время выполнения зависит от модели; Границы O (m), O (m log n) и O (mn) фактически показаны для трех разных моделей, хотя последняя оценка считается более реалистичной.

Приведенный выше текст взят из Algorithms and data analysis by Wessis.

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

1. Как мы получаем 2/5 в приведенном выше описании?
2. Как мы получаем 8/11 в приведенном выше описании?
3. Автор описал только две модели, но в конце абзаца упоминается для разных моделей, что такое третья модель?

Спасибо за вашу помощь

Вот ответ на первые два вопроса:

1. Учитывая пять деревьев A, B, C, D, E, какова вероятность того, что E включено в пару случайно выбранных деревьев?

   Поскольку существует 10 возможных пар (AB, AC, AD, AE, BC, BD, BE, CD, CE, DE) и четыре из них (AB, AC, AD, AE) содержат A, вероятность равна 4/10 = 2/5.

2. Учитывая пять деревьев A = {a}, B = {b}, C = {c}, D = {d}, E = {e, f, g, h} какова вероятность того, что элемент E включен в пару случайно выбранных элементов (где нет двухэлементы выбираются из одного дерева)?

   Существует 22 пары элементов (ab, ac, ad, ae, af, ag, ah, bc, bd, be, bf, bg, bh, cd, ce, cf, cg, ch, de, df, dg, dh), и 16 из них включают один из (e, f, g, h) вероятность равна 16/22 = 8/11.