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]<ref name = "while"/>. Правда, если в этом примере точки обрабатываются в обратном порядке, то суммарное количество обработанных точек линейно зависит от <tex>n</tex> и <tex>d</tex>. Тем не менее, существуют примеры, для которых любой порядок обработки приводит к экспоненциальной зависимости числа порожденных точек от размерности пространства <tex>d</tex> и эта зависимость близка к <tex>n^d</tex> <ref name="while">
While, L., Hingston, P., Barone, L., Huband, S.: A Faster Algorithm for Calculating Hypervolume. IEEE Transaction on Evolutionary Computation, Vol.10, No. 1, pp 29–38 (2006)</ref>.
