简单for循环是否具有指数复杂性？

Question

算法的时间复杂度定义为其运行所需的时间量，作为输入长度的函数。

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

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

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

但我们永远不会听到任何人说，这样的for-loop程序在其输入（存储n所需的位）中是指数的。为什么会这样？我看到的唯一区别是，这是一个程序，时间复杂度是为算法定义的。但是，即使是这样，当我们想要对一个程序进行粗略的时间复杂度分析时，为什么不考虑这一点？

编辑：进一步澄清：我发现有理由声称它在输入中是指数型的（可能是错误的=）。如果是这样，那么如果一个简单的for循环是指数的，那么其他的难题呢？显然，这对于今天的任何人来说都不是一个问题。为什么不是呢？为什么与其他困难问题（EXP、NP-hard等）相比，这没有（太多）现实意义？注：我使用的是它用来定义NP难问题的方式。

Answer 1

从技术上讲，for循环或就此而言，所有线性程序在其输入中都是指数的，但这并不用于解释其运行时，因为很简单，运行时是如何定义的，它随输入的变化而变化。在这些问题中，输入位的数量被认为是恒定的，例如，您可能只为整数输入定义算法，因此其输入始终为32位，因此它被认为是恒定的，因为即使n的值改变，位的数量也不会改变，所以常数项不能用于定义算法的增长，因此忽略。

Answer 2

一个函数所花费的时间是由某个东西参数化的函数。通常它是输入的大小，但有时它是一个显式参数，当你描述一个函数时，它取决于你是否清楚你的意思。因为从上下文中参数化通常是“显而易见的”，所以它经常被省略，当参数化对每个人都不明显时，这会导致很多混乱。

当你加上“复杂性”这个词时，那意味着不是描述一个函数，而是说它属于一个特定的函数类。它并不排除说明函数是什么及其参数是什么的需要。

Answer 3

详细阐述了@Anonymous的答案：你应该问的问题是“什么是指数？”最终，这是否是指数时间取决于n如何呈现给你。

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

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

希望这有帮助！