Профиль хода: кто съедает бюджет и как он растёт

import random

N = 40                                   # карта N × N
rabota = {}

def schet(modul, k):
    rabota[modul] = rabota.get(modul, 0) + k

def pole(cel):
    # модуль пути: поле расстояний от цели, обход в ширину
    dist = [-1] * (N * N)
    dist[cel] = 0
    och = [cel]
    golova = 0
    while golova < len(och):
        v = och[golova]
        golova = golova + 1
        for u in [v - N, v + N, v - 1, v + 1]:
            schet("путь", 1)
            if 0 <= u < N * N and (u // N == v // N or u % N == v % N):
                if dist[u] == -1:
                    dist[u] = dist[v] + 1
                    och.append(u)
    return dist

def ryadom_pary(otryady):
    # модуль обзора: все пары ближе 4 клеток - перебором
    par = 0
    for i in range(len(otryady)):
        for j in range(i + 1, len(otryady)):
            schet("обзор", 1)
            a = otryady[i]
            b = otryady[j]
            if max(abs(a // N - b // N), abs(a % N - b % N)) <= 4:
                par = par + 1
    return par

def ryadom_setka(otryady):
    # тот же модуль на равномерной сетке 8 × 8
    kor = {}
    for i in range(len(otryady)):
        k = (otryady[i] // N) // 8 * 100 + (otryady[i] % N) // 8
        if k not in kor:
            kor[k] = []
        kor[k].append(i)
    par = 0
    for i in range(len(otryady)):
        r = (otryady[i] // N) // 8
        c = (otryady[i] % N) // 8
        for dr in [-1, 0, 1]:
            for dc in [-1, 0, 1]:
                for j in kor.get((r + dr) * 100 + c + dc, []):
                    if j > i:
                        schet("обзор", 1)
                        a = otryady[i]
                        b = otryady[j]
                        if max(abs(a // N - b // N),
                               abs(a % N - b % N)) <= 4:
                            par = par + 1
    return par

def hod(n_otryadov, setka):
    random.seed(n_otryadov)
    otryady = []
    for i in range(n_otryadov):
        # клетки отрядов могут совпасть - для замера цены это неважно
        otryady.append(random.randint(0, N * N - 1))
    pole(N * N // 2)                     # одна общая цель - одно поле
    if setka:
        ryadom_setka(otryady)
    else:
        ryadom_pary(otryady)

for sposob in [["обзор перебором:", False], ["обзор сеткой:   ", True]]:
    rabota["путь"] = 0
    rabota["обзор"] = 0
    hod(140, sposob[1])
    vsego = rabota["путь"] + rabota["обзор"]
    print(sposob[0], "путь", rabota["путь"], "| обзор", rabota["обзор"],
          "| доля обзора", round(100 * rabota["обзор"] / vsego), "%")

обзор перебором: путь 6400 | обзор 9730 | доля обзора 60 %
обзор сеткой:    путь 6400 | обзор 2762 | доля обзора 30 %

import math
import random

def ryadom_pary(otryady, N):
    # работа перебора - число проверенных пар; само сравнение
    # расстояний здесь опущено, нам нужна только цена
    proverok = 0
    for i in range(len(otryady)):
        for j in range(i + 1, len(otryady)):
            proverok = proverok + 1
    return proverok

def ryadom_setka(otryady, N):
    # равномерная сетка 8 × 8: пары только из своей и соседних корзин;
    # тоже считаем одни проверки
    kor = {}
    for i in range(len(otryady)):
        k = (otryady[i] // N) // 8 * 1000 + (otryady[i] % N) // 8
        if k not in kor:
            kor[k] = []
        kor[k].append(i)
    proverok = 0
    for i in range(len(otryady)):
        r = (otryady[i] // N) // 8
        c = (otryady[i] % N) // 8
        for dr in [-1, 0, 1]:
            for dc in [-1, 0, 1]:
                for j in kor.get((r + dr) * 1000 + c + dc, []):
                    if j > i:
                        proverok = proverok + 1
    return proverok

def zamer(n, N, setka):
    random.seed(n)
    otryady = []
    for i in range(n):
        # клетки отрядов могут совпасть - для замера цены это неважно
        otryady.append(random.randint(0, N * N - 1))
    if setka:
        return ryadom_setka(otryady, N)
    return ryadom_pary(otryady, N)

# 60, 120, 240 отрядов. Тест удвоения: если работа ~ n^p, при
# удвоении n она растёт в 2^p раз, значит, p = log2(отношения)
sposoby = [["перебор, карта 64:  ", False, False],
           ["сетка, карта 64:    ", True, False],
           ["сетка, карта растёт:", True, True]]
for s in sposoby:
    prosh = 0
    stroka = s[0]
    for n in [60, 120, 240]:
        N = 64
        if s[2]:
            N = round(64 * math.sqrt(n / 60))    # плотность постоянна
        r = zamer(n, N, s[1])
        stroka = stroka + " " + str(r)
        if prosh > 0:
            p = round(math.log2(r / prosh), 1)
            stroka = stroka + " (p≈" + str(p) + ")"
        prosh = r
    print(stroka)

перебор, карта 64:   1770 7140 (p≈2.0) 28680 (p≈2.0)
сетка, карта 64:     216 925 (p≈2.1) 3497 (p≈1.9)
сетка, карта растёт: 216 452 (p≈1.1) 970 (p≈1.1)