1 Свойства и структура алгоритма

Распределение d-мерных векторов по k кластерам
Поскольку на данном шаге для каждой пары векторов xi, i=1,...,n и μj, j=1,...,k, операции вычисления расстояния не зависят друг от друга, они могут выполняться параллельно. Тогда, разделив все вычисление расстояний на n потоков, получим, что в каждом потоке будет выполняться только одна операция вычисления расстояния между векторами размерности d. При этом каждому вычислительному потоку передаются координаты центров всех кластеров μ1,...,μk. Таким образом, параллельная сложность данного шага определяется сложностью параллельной операции вычисления расстояния между d-мерными векторами, Ψddistance и сложностью определения наиболее близкого кластера (паралельное взятие минимума по расстояниям), Ψkmin. Для оценки Ψddistance воспользуемся параллельной реализацией нахождения частичной суммы элементов массива путем сдваивания. Аналогично, Ψkmin=log(k). В результате, Ψddistance=O(log(d)). Таким образом:
Ψk,ddistribute=Ψddistance+Ψkmin=O(log(d))+O(log(k))=O(log(kd))
Пересчет центров кластеров в d-мерном пространстве
Поскольку на данном шаге для каждого из k кластеров центр масс может быть вычислен независимо, данные операции могут быть выполнены в отдельных потоках. Таким образом, параллельная сложность данного шага, Ψk,drecenter, будет определяться параллельной сложностью вычисления одного центра масс кластера размера m, Ψk,drecenter, а так как m≤n⇒Ψd,mrecenter≤Ψd,nrecenter. Сложность вычисления центра масс кластера d-мерных векторов размера n аналогично предыдущим вычислениям равна O(log(n)). Тогда:
Ψk,drecenter≤Ψd,nrecenter=O(log(n))
Общая параллельная сложность алгоритма
На каждой итерации необходимо обновление центров кластеров, которые будут использованы на следующей итерации. Таким образом, итерационный процесс выполняется последовательно^[7]. Тогда, поскольку сложность каждой итерации определяется Ψk,ddistribute и Ψrecenter, сложность всего алгоритма, Ψk−means в предположении, что было сделано i операций определяется выражением
Ψk−means≈i⋅(Ψk,ddistribute+Ψk,drecenter)≤i⋅O(log(kdn))