n 在大 O 复杂度中是什么意思？

Question

在Big-Oh表示法中，n是什么意思？我已经看到了向量的输入大小和长度。如果是输入大小，是否意味着计算机上的内存space？我看到 n 经常与输入大小互换使用。

大哦的例子，

O(n)线性运行次
O(logn) 是对数运行时间。

代码复杂度分析示例，（我正在将输入 n 更改为 m）

def factorial(m):
   product = 1
   for i in range(1, m+1):
      product = product*i
   return product

这是 O(n)。 n 是什么意思？它需要多少内存？也许 n 是指向量中元素的数量？那么，当n=3，单号怎么解释呢？

Answer 1

n 通常表示输入数据量。

例如，取一个包含 10 个元素的数组。要迭代所有元素，您将需要十次迭代。 n 在这种情况下是 10。

在您的示例中，n 也是描述输入数据大小的值。正如您所看到的，您的阶乘实现将需要 n+1 次迭代，因此此实现的渐近复杂度约为 O(n)（注意：我省略了 1，因为它不会改变图片很多）。如果您将传递的变量 n 增加到您的函数，则需要执行更多迭代来计算结果。

Answer 2

O(1) 描述了一种算法，无论输入数据集的大小如何，它总是在同一时间（或 space）执行。

O(N) 描述了一种算法，其性能将线性增长并与输入数据集的大小成正比。

O(N^2)表示一种算法，其性能与输入数据集大小的平方成正比。这在涉及对数据集进行嵌套迭代的算法中很常见。

希望对您有所帮助。

Answer 3

当有人说 O(n) 时，n 可以根据上下文指代不同的事物。当 n 指的是什么不明显时，人们最好明确指出它，但存在几个约定：

当 O-notation 中使用的变量名称也存在于代码中时，它们几乎肯定指的是具有该名称的变量的值（如果它们指的是其他任何东西，那应明确指出）。因此，在您的原始示例中，您有一个名为 n 的变量，O(n) 将引用该变量。
当代码不包含名为 n 的变量且 n 是 O 符号中使用的唯一变量时，n 通常指的是总大小输入的。
当使用多个变量时，从n开始，然后继续字母表（例如O(n*m)），n通常是指第一个参数的大小，m 第二个等等。但是，在我看来，在实际参数名称周围使用 | | 或 len( ) 之类的东西通常更清楚（例如 O(|l1| * |l2|) 或 O(len(l1) * len(l2)) 如果您的参数被称为 l1 和 l2).
在图形问题的上下文中，v 通常用于表示顶点数，e 表示边数。

在所有其他情况下（以及在上述某些情况下，如果有任何歧义），应明确提及变量的含义。

在您的原始代码中，您有一个名为 n 的变量，因此语句 "This is O(n)" 几乎肯定引用了参数 n 的值。如果我们进一步假设我们只计算乘法的次数或循环体执行的次数（或者我们测量时间并假装乘法需要常数时间），则该陈述是正确的。

在您编辑的代码中，不再有名为 n 的变量。所以现在语句 "This is O(n)" 必须引用别的东西。通常人们会假设它指的是输入的大小（这将是 m 中的位数，即 log m）。但是该语句显然是错误的（应该是 O(2^n)，而不是 O(n)），因此原始语句清楚地引用了 n 的值，您通过编辑代码破坏了它。

n 在大 O 复杂度中是什么意思？

What does n mean in big-oh complexity?

complexity-theory

big-o

time-complexity