这个函数的 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) 让我们一起数一下：

我们有最外层循环 (I)、最内层循环 (III) 和中间循环 (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)可以进一步展开为：

为了扩展求和，我使用了等差数列中连续数字求和的公式。

这个函数的 T(s) 方程是什么？

What is the T(s) equation for this function?

algorithm

math

complexity-theory