25
правок
Изменения
м
Нет описания правки
Обработка точек продолжается, пока все точки не будут обработаны. Таким образом, время работы алгоритмы напрямую зависит от количества порожденных точек. Легко заметить, что таких точек не более, чем <tex>n^d</tex>, поскольку каждая координата каждой порожденной точки равна соответствующей координате некоторой точки исходного множества <tex>X</tex>.
К сожалению, эта верхняя оценка является достижимой. Например, если исходное множество <tex>X</tex> имеет вид: <tex>(1, n, n, ..., n), (2, n - 1, n - 1, ..., n - 1), ..., (n, 1, 1, ..., 1)</tex>, и точки обрабатываются в этом порядке, то всего будет обработано <tex>n^{d-1}</tex> точка, что показано в [1]. Правда, если в этом примере точки обрабатываются в обратном порядке, то суммарное количество обработанных точек линейно зависит от <tex>n</tex> и <tex>d</tex>. Тем не менее, существуют примеры, для которых любой порядок обработки приводит к экспоненциальной зависимости числа порожденных точек от размерности пространства <tex>d</tex> и близок к <tex>n^d</tex> [1].
