以 Θ 表示的复杂度

Question

我知道下面的代码被认为是"Linear or Θ(n)"我不明白的是我们是怎么知道的。

假设 n 已被适当地声明并被设置为一个值。

int sum = 0;
for (int i = 0; i < n*2; i++ )
   sum++;

下面是一个额外的循环，据我所知是非线性的，但我的问题是我们如何仅通过查看代码来确定可能的速度？ Θ 复杂性，以 n 表示，更具体地说。

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

Answer 1

在您的第一个示例中，您只有一个 for loop。 i 值线性增加，直到满足条件 i<n*2;。 for 循环的执行时间与 n 的值线性相关，因此其时间复杂度为 O(n) 因为您的 i 值与n。

在您的第二个示例中，您嵌套了 for loops。 i 值线性增加，对于每个 i 值，内部 for loop 执行 n/2 次，因为变量 j 在每次迭代中增加 2。由于外循环执行 n 次，而内循环每次外循环迭代执行 n/2 次，因此此示例的总运行时间为 n*n/2。但通常时间的常数部分可以忽略不计（或有时不考虑）。所以我们可以说它的运行时间是 O(n^2).

Big O 和 Theta 符号的区别，Big O 用于表示增长函数的上界，Theta 用于表示增长函数的紧界。有关差异的更多信息，请参阅 Big O and Theta notation.

之间的差异

Answer 2

大O的概念可以认为是大小n的给定输入每个元素processed/accessed在下面的程序中有多少次？

所以对于你的第一个例子

int sum = 0;
   for (int i = 0; i < n*2; i++ )
      sum++;

n 的大小无关紧要。只对 n 循环运行多少次很重要。所以由于这段代码会循环n*2次，所以它的运行ning次也是n*2次。尽管它会运行 n*2 次，但它被称为线性或 O(n) 的原因是因为我们对运行ning 时间在 n 的天文大值时的增长感兴趣。到那时，前面的2乘数就变得无关紧要了，这就是为什么它是o(n)。

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

在此示例中，程序将运行 n*(n/2) 次。

n times in the i loop and n/2 times in the j loop

同样，由于我们感兴趣的是这个函数在 n 的天文数字值很大时的增长，n 的 1/2 因子变得无关紧要，使得运行ning 时间 n*n，或 n ^2

以 Θ 表示的复杂度

Complexity in terms of Θ

java

time-complexity