一个简单的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等)相比,为什么这不会产生(很多)现实世界的影响？注意:我正在用它来定义NP-Hard问题.

Answer 1

详细阐述@Anonymous 的回答：您应该问的问题是“指数级的是什么？” 最终，这是否是指数时间取决于 n 呈现给您的方式。

如果 n 是使用 O(log n) 位的显式二进制整数，则该函数将以伪多项式时间运行（技术上是输入位数的指数，但输入数值的多项式）。这就是为什么像试除法这样的简单素性测试算法（将 n 除以 2 到 √n 之间的所有数字，看看其中是否有一个因子）在技术上以指数时间运行，尽管它们的运行时间确实是 O(√n)。

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

希望这可以帮助！