一个关于时间复杂度的问题

2024-11-30 04:34:40

推荐回答（5个）

回答1：

这是个二重循环，第一个for从1到n，总共执行n次，而第二个for语句由第一个for语句中的n获得其本次执行的次数，分别为1，2，3，…，n。而时间复杂度是以执行次数最多的那个语句为结果进行计算的，也就是S执行的频数，这里，S的频数与第二个for语句相同。所以1+2+…+n=n(n+1)/2。时间复杂度为O(n2)。

回答2：

1+2+...+n=n(n+1)/2

回答3：

就是加起来:1+2+...+n=n(n+1)/2

回答4：

循环嵌套，共执行n（n+1）次

回答5：

首先，段代码的时间复杂度不为n(n+1),而应该为n！，也就是n的阶乘。
算法：看循环中的代码随着N的变化执行多少次，这里代码为S；

外层循环一共执行n次。
内层对于每一个具体的i执行i次。
因此s的执行总次数为 1*2*3…*n，也就是n的阶乘次。

ps：关于算法复杂度的问题你可以看看清华出版的数据结构，好像第一章中有讨论到。其实大多数数据结构的书都会谈到复杂度的概念及计算方法。