Как растёт число узлов по уровням
На первом уровне находится a узлов. Каждый порождает q новых, поэтому на втором уровне их a·q, на третьем a·q², и в общем случае на k-м уровне a·q^(k−1). Это геометрическая прогрессия со знаменателем q.
Чем больше ветвление, тем быстрее растёт число узлов: при q = 3 десятый уровень содержит уже 19 683 узла, а при q = 2 — лишь 512.
Формула суммы геометрической прогрессии
Сумма первых n членов равна S = a·(qⁿ − 1)/(q − 1) при q ≠ 1. Числитель содержит qⁿ, поэтому сумма растёт экспоненциально и быстро становится огромной.
При q = 1 формула теряет смысл из-за деления на нуль, но тогда все уровни одинаковы, и S = a·n. Калькулятор учитывает этот случай отдельно и не выдаёт ошибки.
Разбор числового примера
Организатор приглашает троих, каждый из них — ещё троих, цепочка идёт 10 уровней. Сумма равна (3¹⁰ − 1)/2 = 29524: столько человек вовлечено на всех уровнях, включая самого организатора.
Для двоичного дерева глубиной 8 уровней получаем 2⁸ − 1 = 255 вершин, а для 5 корней с ветвлением 4 и 4 уровнями — 5·85 = 425 узлов.
Двоичное дерево и степени двойки
Для q = 2 и одного корня сумма равна 2ⁿ − 1. Это известное соотношение: полное двоичное дерево с n уровнями содержит на единицу меньше узлов, чем 2ⁿ, а последний уровень вмещает ровно половину всех узлов плюс один.
Такие числа важны в информатике: глубина дерева поиска растёт как логарифм числа элементов, поэтому миллиону элементов достаточно около 20 уровней.
Реальность против идеальной модели
В жизни цепочки быстро затухают: не все приглашённые продолжают рассылку, и многие получают приглашения по нескольку раз. Фактический охват оказывается намного меньше теоретического.
Поэтому результат следует понимать как верхнюю границу. Для оценки реального охвата нужны данные о доле откликнувшихся на каждом уровне, и тогда коэффициент ветвления заменяют средним значением, меньшим единицы.
Что можно ввести неправильно
Распространённая ошибка — задать число уровней без учёта первого. Если считать только приглашённых, исключив организатора, из результата нужно вычесть число первого уровня.
Вторая ошибка — путать число приглашений каждым с общим числом приглашённых на уровне. Ветвление q относится к одному узлу, а не ко всему уровню.
Как быстро растёт сумма
Геометрическая сумма удваивается или утраивается с каждым уровнем и поэтому быстро превосходит любые разумные оценки. Уже при ветвлении 3 за 15 уровней получается более семи миллионов узлов, а при ветвлении 10 — миллиарды.
Эта скорость роста объясняет, почему экспоненциальные процессы кажутся «внезапными»: первые уровни малы, а последний уровень содержит значительную долю всех узлов — примерно (q − 1)/q от общей суммы.
Практический вывод: прежде чем планировать рассылку или структуру из многих уровней, сначала прикиньте верхнюю границу по формуле, а затем скорректируйте её на долю участников, реально продолжающих цепочку.
Формула расчёта
S = a·(qⁿ − 1) / (q − 1), при q = 1: S = a·n
Проверенные примеры
Один организатор, каждый приглашает троих, 10 уровней. Сколько всего участников?
S = (3¹⁰ − 1)/(3 − 1) = 59048/2 = 29524.
Корень один, каждая вершина имеет двух потомков, 8 уровней.
S = 2⁸ − 1 = 255 вершин.
Как пользоваться онлайн-калькулятором
- Определите, сколько узлов на первом уровне.
- Узнайте, сколько новых узлов порождает каждый.
- Укажите число уровней, включая первый.
- Нажмите «Вычислить», чтобы получить общее число узлов.