Сложность этого алгоритма

Question

Поэтому у меня есть алгоритм, который идет как это:

for i=0:360 

C... 

for j=0:a_j[i] 

    C... 

    for t=0:a_t[i][j] 

    C... 
    end 
end 
end 

Так что есть три петли, но обе внутренние циклы зависят от величины внешних контуров. Как я могу измерить сложность записи Big O?

Также, если у меня есть привязки памяти между этими циклами? Они считаются Cs?

Answer 1

Вы ничего не говорите о остальной части кода, поэтому, полагая, что остальные являются примитивными операциями постоянной сложности.

Если записи из двух массивов меньше постоянного значения, то сложность O(1) - обработка не зависит от какого-либо значения, введенного вне вашего кода. Если они являются функциями входной переменной, то сложность зависит от функций, которые они обрабатывают в этих массивах, и в этом случае вы должны быть более конкретными.

Answer 2

Я не уверен, что именно a_j и a_t - это точно. Если a_j и a_t - константа, то сложность O(1). Если a_j и a_t - это n, что может означать входные переменные, то мы должны вычислить сложность.

Одним словом, сложность этой программы определяется путем определения a_j и a_t.

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

Вот код, написанный на питоне:

ret = 0 
for i, v in a_j: 
    ret += v * sum(a_t[i]) 
if not ret: ret = 1 
ret *= 360 

Надеется, что это помогает.