操纵 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 表示法及其微妙之处。我一直在寻找类似于第一个例子的案例，但我很难找到这样一个具体的答案。

Answer 1

当谈论 O 表示法时，n 本身的重新分配并不是真正重要的。作为一个例子，考虑一个简单的 for 循环：

for i in range(n):
   do_something()

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

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

并且相当于您提出的第一个递归函数。因此，真正重要的是与输入大小（即 n 的原始值）相比，完成了多少计算。
因此，所有这三种算法都是 O(n) 算法，因为这三种算法每次都会将“输入大小”减少 1。即使他们将其增加 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。

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

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