algorithm - 一个简单的 for 循环是否具有指数复杂度？

Question

算法的时间复杂度定义为它运行所花费的时间量，它是输入长度的函数。

如果我在 C 中有一个简单的 for 循环函数，它针对给定的输入 n 运行，那么:
n 的长度是 log n(表示它所需的位数)。由于输入是 log n 并且循环运行 n 次，因此代码在其输入长度 ( 2^(log n) = n)) 中呈指数运行多次
C代码:

int forfunction(unsigned int n){
  unsigned int i=0;
  for(;i<n;i++){
    // do something ordinary
  }
  return 0;
}

这个for循环就是一个例子。

但我们永远不会听到有人说，这样的 for 循环程序在其输入(存储 n 所需的位)方面是指数级的。为什么会这样？我看到的唯一区别是这是一个程序，时间复杂度是为算法定义的。但即使是，那为什么当我们想要对程序进行粗略的时间复杂度时，这不会产生影响/被考虑在内？

编辑:进一步澄清:我发现声称它的输入是指数的是合理的(可能是错误的=))。如果是这样，那么如果一个简单的 for 循环是指数级的，那么其他难题呢？显然，今天的任何人都不会担心这个 for 循环。为什么不是呢？与其他难题(EXP、NP-Hard 等...)相比，为什么这对现实世界没有(太多)影响？注意:我使用 hard 来定义 NP-Hard 问题。

Answer 1

详述@Anonymous 的回答:您应该问的问题是“什么 呈指数增长？”最终，这是否是指数时间取决于 n 如何呈现给您。

如果使用 O(log n) 位将 n 作为显式二进制整数提供给您，则此函数将以伪多项式时间运行(技术上输入位数的指数，但输入数值的多项式) .这就是为什么简单的素数测试算法，如试验除法(将 n 除以从 2 到 √n 的所有数字，看看它们是否是因数)在技术上以指数时间运行，即使它们确实以 O(√n) 的时间运行。

另一方面，如果使用 O(n) 位隐式地给你 n(可能是给定邻接矩阵的图形中的节点数，或者可能是给定字符串的字符串中的字符数) ，那么运行时间是多项式的，因为输入至少具有线性大小并且完成了线性工作。这就是为什么运行时间为 O(m + n) 形式的 DFS 或 BFS 等算法以多项式时间运行的原因:输入中的位数为 Ω(m + n)。

希望这对您有所帮助!