小编dig*_*y91的帖子

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

如果我在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问题.

关于线程是否获得自己的堆栈,有各种各样的问题.但是,我无法理解操作系统如何实现或操作系统通常如何为每个线程实现一个堆栈.在OS书籍中,程序的内存布局如下所示:

请注意,它可以被视为连续的内存块(虚拟内存).我想象虚拟内存空间的某些部分在线程的堆栈之间划分.这让我想到了这个问题的第二部分:一个流行的技术面试问题涉及尝试使用单个数组实现3个堆栈.这个问题是否与解决线程堆栈的实现直接相关.

我总结了我的问题:

1. 现代操作系统如何说,Linux为不同线程的堆栈划分内存空间？
2. "3个堆栈使用1个数组"是否与上述问题直接相关或答案？

PS:也许用于解释内存如何划分为不同线程堆栈的图像最好解释一下.