VecutePoint

Алгоритм выборки пространственных точек, сложность которого составляет O(n), где n — количество элементов в выборке.

Суть алгоритма заключается в том, что данные представляются в виде матрицы, после чего случайным образом выбирается одно значение из матрицы меньшего размера.

Например, возьмём одномерный массив данных {8, 2, 7, 4, 9, 6, 7, 8, 11, 2, 5, 4, 5} и применим к нему алгоритм выборки с шагом 5. Диапазон значений для выборки: от 1 до 11. Шаг выборки (step) равен 2. В результате получаем матрицу: [1-3], [3-5], … [9-11].

После этого данные распределяются по матрице. На выходе получаем все значения из этой матрицы. Это и есть результат выборки.