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 的二次函数？

score 6 · Accepted Answer

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

score 2 · Accepted Answer

2

你将循环 N 三轮..所以我说：O(n^3)

于 2013-09-08T00:24:18.007 回答

score 0 · Accepted Answer

算法：

Sum = 0; ~ 1

 for i=1 to N^2 do: ~ 1+2N^2
   for j=1 to N do: ~ (1+2N) * N^2
    'Sum += 1; ~ 1 * N * N^2

时间复杂度：

Time = 1 + 1+2N^2 + (1+2N)*N^2 + 1 * N * N^2

Time = 2 + 2N^2 + N^2 + 2N^3 + N^3

Time = 2 + 3N^2 + 3N^3

O(Time) = O(2 + 3N^2 + 3N^3) ~ O(N^3)

3 回答 3