寻找

Question

我给出的循环伪代码嵌套循环的复杂性：

其中“为”等同于“< =”

sum = 0; 
for i = 1 to n 
    for j = 1 to i^3 
    for k = 1 to j 
     sum++ 

我所知道的最外层循环运行n倍。 虽然两个内部循环也运行n times？ （使得整个复杂O(n^3)

实例，其中对于n = 5 然后：

1 <= 5  2<= 5 
j = 1 <= 1^3 2 <= 2^3 = 8 
k=1 <= 1  2 <= 2 

，这将继续n次的每个循环，使它n^3

Answer 1

这似乎是一个棘手的？问题，那些内环比n更复杂

外环是n。 下一个循环进入至i^3。在外部循环结束时，我将等于n。这意味着这个循环最后将在n^3。从技术上讲，这将是(n^3)/2，但我们忽略，因为这是大O. 第三个循环去j，但在前一个循环的末尾j将等于i^3。而且我们已经确定i^3等于n^3。

所以它看起来像：

• 第一环：n
• 第二环：n^3
• 第三环：n^3

它看起来像它涉及到n^7。我希望别人来验证这一点。爱是爱大O.

Answer 2

您可以使用六西格玛符号明确地展开在循环的基本操作的数量（让sum++是一个基本操作）：

凡

• (i)：Partial sum formula from Wolfram Alpha。
• (ii)：Expanding the expression from Wolfram Alpha。

因此，使用Big-O符号的复杂性是O(n^7)。