Как я могу сделать анализ моего алгоритма во время выполнения?

Question

Предположим, у нас есть несколько сервисов с разными входными параметрами. Сначала мы генерируем список чисел (cache_slices = [0,00, 0,01, ..., 1,00]), которые представляют ось X. Затем для каждого из этих значений мы вычисляем backhaul_slices, которые представляют линейное выражение с cache_slices (backhaul_slice = a * cache_slice + b, с действительными числами a и b).

После этого мы вычисляем абсолютное значение разницы между каждым кортежем (backhaul_slice, cache_slice) в abs_diff_list. Затем мы перебираем список abs_diff_list до тех пор, пока не найдем его минимальное значение и не добавим кортеж в список. Это должно быть сделано для всех сервисов N.

Это код Python для алгоритма, где гамма (i, бета) представляет функцию для вычисления backhaul_slice по cache_slice:

cache_slices = [beta/100 for beta in range(101)]
tuples_list = []
for i in range(num_services):
    backhaul_slices = [gamma(i,beta) for beta in cache_slices]
    abs_diff_list = [abs(gamma(i,beta)-beta) for beta in cache_slices]
    for j in range(len(abs_diff_list)):
        if abs_diff_list[j] == min(abs_diff_list):
            tuples_list.append((backhaul_slices[j],cache_slices[j]))
            break

Как я могу выполнить анализ алгоритма во время выполнения (лучший, средний и наихудший случай)?

Answer 1

Как уже упоминалось в комментарии, сложность равна квадратичной c, потому что min пересчитывается на каждой итерации. Снятие его с l oop сделает сложность линейной. Однако даже это является излишним. Возможна постоянная временная сложность.

Вы стремитесь минимизировать abs(gamma(i,beta)-beta). Согласно вашему объяснению, gamma является линейной функцией: a[i]*beta + b[i]. Следовательно, минимизируемый функционал abs((a[i] - 1) * beta + b[i]). Его минимум достигается, когда beta около root из (a[i] - 1) * x + b[i] == 0, то есть beta должно быть около -b[i] / (a[i] - 1). Есть только два кандидата для тестирования (в угловом случае, когда root не принадлежит интервалу [0.0 ... 1.0], требуется только один тест). Постоянная сложность времени.