java 如何从代码片段计算等式中的T(n)？

jpfvwuh4 于 2023-02-02 发布在 Java

关注(0)|答案(1)|浏览(108)

我在将代码片段转换为计算T（n）的方程时遇到了问题，下面是一个示例代码片段：
a = b + c; d = a + e;
这个特定的问题要求确定T（n）。我应该如何去做呢？另一个示例代码如下所示：

sum = 0;
for (i=0; i<3; i++)
    for (j=0; j<n; j++)
        sum++;

我已经尝试按照其他类似问题的说明和例子来做了，但我还是被这个方程是如何精确求解的卡住了，下面是我目前所知道的一个例子和结果：
代码：

sum = 0;
i = 1;
while (i <= N)
{
    sum = sum + 1;
    i++;
}

结果是这样的：T（N）= 2+（Σ，N在上，i +1在下）* 2，最后简化为2 + 2N，我不确定这个结果是怎么得到的。

Java

来源：https://stackoverflow.com/questions/75301656/how-do-you-calculate-tn-in-an-equation-from-a-code-fragment

1条答案

按热度按时间

nzk0hqpo1#

下面是解决这个问题的方法：

sum = 0;                 // 1 - O(1)
for (i=0; i<3; i++)      // This will run 3x times - O(3)
    for (j=0; j<n; j++)  // This will run n times (O(n)), meaning the sum will be increased n times 
        sum++;

然后你可以写T(n)=1+3*(1+n+2n)≈1+3n，这意味着这个代码的时间复杂度是O（n）。
一般来说，当你看到一个简单的for循环时，你可以通过条件语句来判断它的复杂度，对于j<n，复杂度是O（n），对于i<3，复杂度是O（3）。

赞(0）回复(0）举报 2023-02-02

我来回答

java 如何从代码片段计算等式中的T(n)？

1条答案

相关问题

热门标签

最新问答