Пусть N — количество частиц, (равномерно) расположенных в пространстве,
Nb — количество потенциальных контактов частицы i (например, соседних частиц), Nb<<N,
Nc — количество реальных контактов частицы i, Nc<=Nb
NС — общее количество контактов между частицами в системе, NC = SUM(Nc)/2

Как рассчитать сложность алгоритма, определяющего NC?

В простейшем случае надо проверить на контакт все N(N-1)/2 потенциальных пар => сложность алгоритма расчета NC будет O(N^2).

Если теперь для частицы i определить Nb, тогда для нахождения Nc для этой частицы надо проверить только Nb(Nb-1)/2 потенциальных пар.
А как теперь оценить сложность нахождения полного NC?
Я думал, что так как всего N частиц, и на каждую по Nb(Nb-1)/2 проверок, => N*Nb(Nb-1)/2 всего проверок => O(N*Nb^2).
Но для частицы j, находящейся в потенциальном контакте с частицей i надо проверить уже на Nb-1 соседей меньше, а для частицы k, находящейся одновременно в контакте c обеими частицами i и j, проверять надо уже Nb-2, и т.д. Как это учитывать? Может быть тогда имеем (N/Nb)*Nb(Nb-1)/2 всего проверок? и сложность O(N*Nb)?

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

__>Пусть N — количество частиц, (равномерно) расположенных в пространстве,
__>Nb — количество потенциальных контактов частицы i (например, соседних частиц), Nb<<N,
__>Nc — количество реальных контактов частицы i, Nc<=Nb
__>NС — общее количество контактов между частицами в системе, NC = SUM(Nc)/2

__>Как рассчитать сложность алгоритма, определяющего NC?

__>В простейшем случае надо проверить на контакт все N(N-1)/2 потенциальных пар => сложность алгоритма расчета NC будет O(N^2).

__>Если теперь для частицы i определить Nb, тогда для нахождения Nc для этой частицы надо проверить только Nb(Nb-1)/2 потенциальных пар.
__>А как теперь оценить сложность нахождения полного NC?
__>Я думал, что так как всего N частиц, и на каждую по Nb(Nb-1)/2 проверок, => N*Nb(Nb-1)/2 всего проверок => O(N*Nb^2).
__>Но для частицы j, находящейся в потенциальном контакте с частицей i надо проверить уже на Nb-1 соседей меньше, а для частицы k, находящейся одновременно в контакте c обеими частицами i и j, проверять надо уже Nb-2, и т.д. Как это учитывать? Может быть тогда имеем (N/Nb)*Nb(Nb-1)/2 всего проверок? и сложность O(N*Nb)?


1. Не совсем понятно описанна система, пример возможного описания: имеется 2D пространство размером Lx * Ly заполненное частицами радиуса R. Частицы распределены случайно. Количество частиц N. Частицы не могут проникать друг в друга и т.д.

2. Если необходимо только прикинуть количество контактов то можно вывести формулу на основе которой можно без бегатни по частицами расчитать некое усреднённое значение контактов.

3. Если необходимо вычислить точное число контактов то задача сводиться к поиску для каждой частицы соседних частиц центры которых расположенны на расстоянии 2 радиуса частицы от центра целевой частицы.
Время работы хорошего алгоритма для задачи как описанно в пункте №1 исходя из моего личного опыта будет равно:
Coef1 * N* Log(N) + Coef2 * MaxCountNearPoints * N

Coef1, Coef2 — коэффициенты пропорциональности.

Первый член в выше приведённой формуле перед операцией сложения практически равен нулю, это член появляется при предварительной сортировки вспомогательного массива с помощью метода "Быстрая сортировка", кстати на количестве частиц больше 1 000 000 быструю сортировку можно выкинуть и заменить на другую которая имеет зависимость почти равную Coef3 * N.

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

На реальных задачах второй член превалирует над первым так что время работы алгоритма можно оценить как O(MaxCountNearPoints * N)
Я привёл зависимости для алгоритма который достаточно сложен чтоб его можно было в посте по быстрому описать, но зависимости реальные т.к. существует его реализация которая шустро пашет без проблем с 1999 года.

По поводу:
__>....для частицы j, находящейся в потенциальном контакте с частицей i надо проверить уже на Nb-1 соседей меньше, а для частицы k, находящейся одновременно в контакте c обеими частицами i и j, проверять надо уже Nb-2, и т.д.........
Каждый контакт будет посчитан два раза, так что полученное количество контактов поделим на два и не будем париться.