Что такое уравнение T (s) для этой функции?

Question

Какое точное время выполнения этой функции?

, и я учусь на CS, поэтому я хочу, чтобы некоторые ресурсы помогли рассчитать T (s). ), но на самом деле мне нужна помощь в этом коде.

int function(int arr[], int s)
{
    // arr is array of size s
    int m = 0;
    for (int i = 1; i <= s; i++)
    {
        for (int j = i; j <= s; j++)
        {
            int sum= 0;

            for (int k = i; k <= j; k++)
                a+= arr[k];

            m= max(a, m);
        }
    }
    return m;
}

Answer 1

Поскольку n не является переменной в этой процедуре, T(n) = 1

Предполагая, что вы на самом деле ищете T(s), давайте посчитаем это вместе:

У нас есть самый внешний l oop (I), самый внутренний l oop (III) и средний l oop (II) и T_I (s) - это то, что мы ищем:

T_III(i,j) = j-i+1
 T_II(i,s) = sum(T_III(i, j) for j in [i, s])
    T_I(s) = sum(T_II(i, s) for i in [1, s])

T_I(s) может быть дополнительно расширен на:

Чтобы расширить суммы, я использовал формулу для суммирования последовательных чисел в арифметическом c последовательность.