Поиск ближайшей пары точек методом грубой силы - EcsFlash/DataTypes GitHub Wiki

Во множестве точек найти две, находящиеся ближе всех, расстояние здесь может считаться как угодно. в нашем случае будет евклидово. Входные данные - список P состоящий из n>=2 точек p1 = (x1,y1), p2 = (x2,y2) ... pn = (xn,yn); выходные данные: индексы index1 и index2 - пары ближайших точек.

type Point struct {
	X, Y float64
}

func FindMinDistance(p []Point) (int, int) {
	minDistance := math.Inf('+')
	resultPoint1 := -1
	resultPoint2 := -1
	for i := 0; i < len(p)-1; i++ {
		for j := i + 1; j < len(p); j++ {
			curDistance := math.Sqrt(math.Pow(p[j].X-p[i].X, 2) + math.Pow(p[j].Y-p[i].Y, 2)) //стандартная формула расстояний между двумя точками
			if minDistance > curDistance {
				minDistance = curDistance
				resultPoint1 = i
				resultPoint2 = j
			}
		}
	}
	return resultPoint1, resultPoint2
}

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

┌────────────┬────────────────┬──────────────────┬────────────────┐
│            │  Лучший случай │  Средний случай  │ Худший случай  │
├────────────┼────────────────┼──────────────────┼────────────────┤
│ **Время**  │     O(n²)      │      O(n²)       │     O(n²)      │
├────────────┼────────────────┼──────────────────┼────────────────┤
│ **Память** │     O(1)       │      O(1)        │     O(1)       │
└────────────┴────────────────┴──────────────────┴────────────────┘

Анализ сложности

Временная сложность

  • Внешний цикл: выполняется ( n-1 ) раз, где ( n ) — количество элементов в массиве.
  • Внутренний цикл: для каждого шага внешнего цикла, внутренний цикл выполняется ( n-i-1 ) раз.
  • Основная операция: сравнение/вычисление дистанции

image