algorithm - 大O，算法分析

Question

我想知道以下每个语句的大 O 表示法是什么:

Sum = 0;
 for i=1 to N^2 do:
   for j=1 to N do:
    'Sum += 1;

Sum = 0 肯定是 O(1)，因为它只会执行一次。但是我对第二个语句感到困惑，它应该是 O(N) 因为它是第一个循环吗？或者它应该是 O(N^2) 因为 N^2 是关于变量 N 的二次函数？

Answer 1

第一个循环是 O(N²) 因为它执行了 N² 个步骤。这些步骤中的每一步都执行内部循环，其中涉及 N 个步骤，因此有 N² * N 或 N³ 个步骤，算法为 O(N ³).