Вопрос(ы) относительно вычислительной мощности, прогнозирования времени, необходимого для получения результата

Могу ли я предсказать время, необходимое для этого, используя данные, которые у меня есть из более низких значений q? Как?

Обычно вы должны иметь возможность определить время работы вашего алгоритма с точки зрения ввода. Обратитесь к большой нотации O.

Если я правильно понял ваш вопрос, вам не следует тратить часы на вычисление матрицы 36x36, удовлетворяющей вашим условиям. Скорее всего, вы застряли в бесконечном цикле или что-то в этом роде. Было бы более понятно, если бы вы могли поделиться фрагментом кода.

Есть ли лучший алгоритм для выполнения этого за меньшее время?

Что ж, я попытался сделать то, что вы описали, и это работает за O (q) (при условии, что количество строк постоянно).

import random

def rotate(arr):
    return arr[-1:] + arr[:-1]

y = set([i for i in range(1, 37)])

n = 36
q = 36

res = []

i = 0
while i < n:
    x = []
    for j in range(q):
        if y:
            el = random.choice(list(y))
            y.remove(el)
            x.append(el)
    res.append(x)
for j in range(q-1):
    x = rotate(x)
    res.append(x)
    i += 1
i += 1

По сути, я выбираю случайные числа из набора {1..36} для i+q-й строки, затем поворачиваю строку q раз и назначаю эти повернутые строки следующим q строкам. Это гарантирует оба упомянутых вами условия.

Как я могу рассчитать среднее количество необходимых циклов? (Используя комбинаторику или иным образом).

Если вы не можете рассчитать время вычислений с точки зрения ввода (код слишком сложен), то подгонка к кривой кажется правильной.

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

1. График q в зависимости от времени
2. Установите кривую,
3. Экстраполируйте на q = 36.

Возможно, вы также захотите построить график зависимости q от log (времени), так как это может дать более простую кривую.