如何计算复杂度？

Question

我是算法的初学者，我不知道如何计算复杂度。

Example:
int x=10,y;
y = x;

上面例子中的复杂度是多少？

谢谢

Answer 1

如果参考O表示法，这应该是O(1)。

Answer 2

在Big O Notation中，这对应于O(1)，这基本上意味着操作的运行时是常量，或者至少小于某个常量。因此，运行时并不依赖于您拥有的输入。你可以从我写的东西中推断出，大O符号只给出了运算的上界。还有其他的符号给出了一个下界等等。

例如，它确实依赖于输入的情况可能是：

int res = 0;
int[] arr = getSomeArray();
foreach (int i in arr)
    res = res + i;

这里的运行时间取决于数组的大小，如果我们将数组的长度设置为变量n，那么这个变量就是O(n)。同样，大O符号并没有指定执行所需的确切时间，但在本例中，只是说我们可以将n乘以某个常量，然后在n*some s内完成。

这里给出了更详细的解释：What is a plain English explanation of "Big O" notation?