操纵 n 对算法的 O 有任何影响吗？

Question

操纵n对算法的O有什么影响吗？

递归代码例如：

Public void Foo(int n)
{
  n -= 1;
  if(n <= 0) return;
  n -= 1;
  if(n <= 0) return;

  Foo(n)
}

n 的重新分配是否影响 O(N)？对我来说听起来很直观...

这个算法是否有 O(N) 通过删除常量？从技术上讲，由于它将 n 递减 2，因此它不会具有与此相同的数学效果：

public void Foo(int n) // O(Log n)
{
  if(n <= 0) return;
  Console.WriteLine(n);
  Foo(n / 2);
}

但是 n 的减半不会对 O(N) 有贡献吗，因为你只触及 n 的一半？需要明确的是，我正在学习 O Notation 及其微妙之处。我一直在寻找与第一个示例类似的案例，但我很难找到这样具体的答案。

Answer 1

在谈论 O 符号时，n 本身的重新分配并不是真正重要的。例如考虑一个简单的 for-loop:

for i in range(n):
   do_something()

在这个算法中，我们做了 n 次。这相当于以下算法

while n > 0:
   do_something()
   n -= 1

并且等价于你给出的第一个递归函数。所以真正重要的是与输入大小（即 n 的原始值）相比完成了多少计算。出于这个原因，所有这三种算法都是 O(n) 算法，因为这三种算法每次都会将 'input size' 减一。即使他们将它增加了 2，它仍然是一个 O(n) 算法，因为使用 O 表示法时常数并不重要。因此下面的算法也是一个O(n)算法。

while n > 0:
    do something()
    n -= 2

或

while n > 0:
    do_something()
    n -= 100000

然而，你提出的第二个递归函数是一个 O(log n) 算法（即使它没有基本情况并且技术上会运行直到堆栈溢出），正如你所写的在评论中。直观地，当每次将输入大小减半时，会发生什么情况，这恰好对应于对原始输入数以二为底的对数。考虑以下因素：

n = 32。算法每次减半：32 -> 16 -> 8 -> 4 -> 2 -> 1。我们总共进行了 5 次计算。等价于 log2(32) = 5.

所以回顾一下，重要的是原始输入大小以及与此输入大小相比完成了多少计算。任何可能影响计算的常数都无关紧要。

如果我误解了你的问题，或者你有后续问题，请随时评论这个答案。

操纵 n 对算法的 O 有任何影响吗？

Does manipulating n have any impact on the O of an algorithm?

algorithm

big-o

computer-science